My debian is not discoverable via its hostname in my LAN.
I have a couple of other ubuntu machines in the LAN and they are all pingable via their hostnames.
on my debian:
pi@raspberrypi ~ $ hostname
raspberrypi
on another machine in the same LAN:
ping raspberrypi
ping: unknown host raspberrypi