First of all I have to google what Avahi is and found the following short summary here: https://help.ubuntu.com/community/HowToZeroconf
After that, I got rid of the notification message, by removing the below file and then starting the Avahi service, since some files where not properly auto-created during installation.
$ sudo rm /var/run/avahi-daemon/disabled-for-unicast-local
$ sudo /etc/ini.d/avahi-daemon start
After that I disabled the Avahi service, because I could not see any reason to autostart it when Ubuntu booted. You can disabled auto-services from System->Administration->Services. The last thing I did was to reboot and the problem was gone.