This has been known for quite some time. Avahi is used service discovery like finding printers. It's similar to Mac OS X's Bonjour service. Unfortunately, when you have a .local domain (which I do) it seems to mess with things. For example, I cannot refer to anything in the .local TLD by name. So to fix it I've been just stopping the service.

sudo /etc/init.d/avahi-daemon stop

This works but isn't a permanent solution. To fully remove Avahi from startup use the update-rc.d command.

$ sudo update-rc.d -f avahi-daemon remove
 Removing any system startup links for /etc/init.d/avahi-daemon ...
   /etc/rc0.d/K86avahi-daemon
   /etc/rc1.d/K86avahi-daemon
   /etc/rc2.d/S14avahi-daemon
   /etc/rc3.d/S14avahi-daemon
   /etc/rc4.d/S14avahi-daemon
   /etc/rc5.d/S14avahi-daemon
   /etc/rc6.d/K86avahi-daemon

This removes the script from the various run time levels and makes my life easier. For more information about this issue take a look at the Avahi and Unicast .local wiki page.