Comment 23 for bug 327362

Ok, then it's multiple ISP:s, which is not surprising of course.

The simplest and best workaround for now is to edit /etc/default/avahi-daemon, change AVAHI_DAEMON_DETECT_LOCAL to 0 and reboot. (alternative is to change to eg. OpenDNS from ISP:s DNS servers, and/or advocating the issue to ISP:s service desk).