Comment 24 for bug 116984

Can you paste your syslog entries for Avahi following a bad startup and successful daemon restart?

From davebv's syslog, it appears that avahi-daemon is being started before an IP address has been assigned to the machine. That's a startup ordering issue (and secondarily a weakness in Avahi's ability to detect changes to the network configuration). That may or may not be the same problem you are experiencing.