Avahi on a windows network.
Make the the domains work correctly.
If you can resolve names with hostname but ssh name does not work and your network is managed by windows servers. The protocol of resolving local names used by MS might be conflicting with the bonjour based resolution that linux and macs use.
Make avahi use a different domain that windows uses by editing /etc/avahi/avahi-daemon.conf and changing the domain from local to something else like alocal. The actual name is irrelevant, as long as it don’t clash with the name being used by the windows network (probably local).
If after a reboot this still not work change the file /etc/nsswitch.conf and make sure that the hosts section don’t contain mdns4 ot mdns4-minimal. It should read something like this :
= /etc/nsswitch.conf = = Example configuration of GNU Name Service Switch functionality. = If you have the `glibc-doc-reference' and `info' packages installed, try: = `info libc "Name Service Switch"' for information about this file. passwd: compat group: compat shadow: compat hosts: files dns networks: files protocols: db files services: db files ethers: db files rpc: db files netgroup: nis
Check the avahi page about this problem here