Right, I've tried to reproduce this with the help of my laptop. After configuring it to make a wireless connection (with the iwl3945 Intel PRO/Wireless driver) on boot, outside of NetworkManager, and installing patched mt-daapd it successfully appears on a wired client's shared library list in Rhythmbox from a fresh boot. Relevant lines of the syslog look like this: May 16 16:13:59 ceres dhclient: Listening on LPF/wlan0/00:1c:bf:90:a4:c0 May 16 16:13:59 ceres dhclient: Sending on LPF/wlan0/00:1c:bf:90:a4:c0 May 16 16:13:59 ceres dhclient: Sending on Socket/fallback May 16 16:13:59 ceres dhclient: DHCPDISCOVER on wlan0 to 255.255.255.255 port 67 interval 4 May 16 16:13:59 ceres kernel: [ 17.384085] wlan0: authenticate with AP ffff88007d0bfac0 May 16 16:13:59 ceres kernel: [ 17.385975] wlan0: authenticated May 16 16:13:59 ceres kernel: [ 17.385980] wlan0: associate with AP ffff88007d0bfac0 May 16 16:13:59 ceres kernel: [ 17.388574] wlan0: RX AssocResp from ffff88007d951026 (capab=0x411 status=0 aid=1) May 16 16:13:59 ceres kernel: [ 17.388580] wlan0: associated May 16 16:13:59 ceres kernel: [ 17.390822] ADDRCONF(NETDEV_CHANGE): wlan0: link becomes ready May 16 16:13:59 ceres mt-daapd[2753]: Firefly Version svn-1696: Starting with debuglevel 2 May 16 16:13:59 ceres mt-daapd[2753]: Error loading plugin /usr/lib/mt-daapd/plugins/ssc-ffmpeg.so: /usr/lib/mt-daapd/plugins/ssc-ffmpeg.so: undefined symbol: avcodec_decode_audio May 16 16:13:59 ceres mt-daapd[2753]: Error loading plugin /usr/lib/mt-daapd/plugins/ssc-script.so: plugin declined to load May 16 16:13:59 ceres mt-daapd[2753]: Plugin loaded: daap/svn-1696 May 16 16:13:59 ceres mt-daapd[2753]: Plugin loaded: rsp/svn-1696 May 16 16:13:59 ceres mt-daapd[2753]: Starting signal handler May 16 16:13:59 ceres mt-daapd[2760]: Starting rendezvous daemon May 16 16:13:59 ceres mt-daapd[2760]: Client connecting May 16 16:14:00 ceres mt-daapd[2760]: Initializing database May 16 16:14:00 ceres mt-daapd[2760]: Full reload... May 16 16:14:00 ceres avahi-daemon[2813]: Found user 'avahi' (UID 110) and group 'avahi' (GID 119). May 16 16:14:00 ceres avahi-daemon[2813]: Successfully dropped root privileges. May 16 16:14:00 ceres avahi-daemon[2813]: avahi-daemon 0.6.23 starting up. May 16 16:14:00 ceres avahi-daemon[2813]: Successfully called chroot(). May 16 16:14:00 ceres avahi-daemon[2813]: Successfully dropped remaining capabilities. May 16 16:14:00 ceres acpid: client connected from 2785[0:0] May 16 16:14:01 ceres avahi-daemon[2813]: No service file found in /etc/avahi/services. May 16 16:14:01 ceres avahi-daemon[2813]: Network interface enumeration completed. May 16 16:14:01 ceres avahi-daemon[2813]: Registering new address record for fe80::21c:bfff:fe90:a4c0 on wlan0.*. May 16 16:14:01 ceres avahi-daemon[2813]: Server startup complete. Host name is ceres.local. Local service cookie is 2860126817. May 16 16:14:01 ceres avahi-daemon[2813]: Registering HINFO record with values 'X86_64'/'LINUX'. May 16 16:14:01 ceres mt-daapd[2760]: Client running May 16 16:14:01 ceres mt-daapd[2760]: Client registering May 16 16:14:03 ceres dhclient: DHCPDISCOVER on wlan0 to 255.255.255.255 port 67 interval 9 May 16 16:14:03 ceres dhclient: DHCPOFFER of 192.168.1.21 from 82.70.152.20 May 16 16:14:03 ceres dhclient: DHCPREQUEST of 192.168.1.21 on wlan0 to 255.255.255.255 port 67 May 16 16:14:03 ceres dhclient: DHCPACK of 192.168.1.21 from 82.70.152.20 May 16 16:14:03 ceres avahi-daemon[2813]: Joining mDNS multicast group on interface wlan0.IPv4 with address 192.168.1.21. May 16 16:14:03 ceres avahi-daemon[2813]: New relevant interface wlan0.IPv4 for mDNS. May 16 16:14:03 ceres avahi-daemon[2813]: Registering new address record for 192.168.1.21 on wlan0.IPv4. May 16 16:14:04 ceres dhclient: bound to 192.168.1.21 -- renewal in 1591 seconds. May 16 16:14:04 ceres mt-daapd[2760]: Starting mp3 scan May 16 16:14:04 ceres mt-daapd[2760]: Starting playlist scan May 16 16:14:04 ceres mt-daapd[2760]: Updating playlists May 16 16:14:04 ceres mt-daapd[2760]: Error scanning MP3 files: No such file or directory May 16 16:14:04 ceres mt-daapd[2760]: Scanned 0 songs in 0 seconds May 16 16:14:04 ceres mt-daapd[2760]: Starting web server from /usr/share/mt-daapd/admin-root on port 3689 May 16 16:14:04 ceres mt-daapd[2760]: Registering rendezvous names May 16 16:14:04 ceres mt-daapd[2760]: Serving 0 songs. Startup complete in 0 seconds You can see mt-daapd and avahi-daemon starting concurrently before an IP has been associated with the wireless interface. As soon as it does, Avahi registers itself on the interface and the service appears on the network. It's possible that this load order doesn't reproduce the race you are experiencing or that the problem lies elsewhere. But that's where my assistance must stop, I'm afraid, since without a reproduction I would not be able to trace the problem. :(