If your DNS resolution is working fine, then turn the avahi-daemon service off. That will solve your problem.
/etc/init.d/avahi-daemon stop
If it does (I think it will, because we have had the same problem), then you need to turn it off permanently so that the next reboot will not start it again. You can do that with sysv-rc-conf (you need to install it first). You could do it with update-rc.d but the manpage says you should not:
Please note that this program was designed for use in package maintainer scripts and, accordingly, has only the very limited functionality required by such scripts. System administrators are not encouraged to use update-rc.d to manage runlevels. They should edit the links directly or use runlevel editors such as sysv-rc-conf and bum instead.
sysv-rc-conf works a lot like chkconfig for Red Hat based distributions.
If you need to do this at a lot of servers, use a configuration management like cfengine. We have this for our cfengine2 setup:
classes:
debian::
# if this does not return 0 then ..
avahi_off = ( !ReturnsZero(/usr/sbin/sysv-rc-conf avahi-daemon) )
shellcommands:
avahi_off::
# ... deactivate the avahi daemon
"/usr/sbin/sysv-rc-conf avahi off" inform=true
"/etc/init.d/avahi... stop" inform=true