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.
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.