I was having a wee bit of trouble getting ping to work for a newly installed zeroconf network. Here follow symptoms and solution:

• The network consisted of several new debian installations and my sparkle-free but reliable apple laptop. I had apt-get installed all packages with avahi in their name. However if I ran avahi-discover on a debian machine it could see the apple but pinging the apple gave a response of "not found".
• I had modified the /etc/nsswitch.conf file to take account of zeroconf addresses when trying to resolve domain names. Google for nsswitch and avahri and you will find lots of sample setups. Mine had this in the critical line (and still works fine):

  hosts:          files dns mdns4
  

• The key is to ask how mdns relates to avahi. Quite simple: apt-cache search for mdns and you will find some packages, mdns-scan and libnss-mdns, that once installed do the trick. I rebooted to get the change to take effect but there are doubtless less crude methods.