I now have access to Ubuntu Gutsy 7.10 which I boot from an USB HD. There is no improvement, as the following log snippets show.
I plugged the eth0 cable at 12:15 which was recognized within 2 seconds by avahi. DHCP only reacted 6 minutes later.
In nm-applet, I've disabled roaming (I'm not aware that the admins here support it, and set DHCP on eth0 instead).

Feb  1 12:10:10 jchlaptop dhclient: No working leases in persistent database - sleeping.
Feb  1 12:14:45 jchlaptop dhclient: DHCPDISCOVER on eth0 to 255.255.255.255 port 67 interval 6
Feb  1 12:14:51 jchlaptop dhclient: DHCPDISCOVER on eth0 to 255.255.255.255 port 67 interval 10
Feb  1 12:15:01 jchlaptop dhclient: DHCPDISCOVER on eth0 to 255.255.255.255 port 67 interval 9
Feb  1 12:15:10 jchlaptop dhclient: DHCPDISCOVER on eth0 to 255.255.255.255 port 67 interval 6
Feb  1 12:15:16 jchlaptop dhclient: No DHCPOFFERS received.
Feb  1 12:15:16 jchlaptop dhclient: No working leases in persistent database - sleeping.
Feb  1 12:15:20 jchlaptop kernel: [32959.104000] eth0: link up, 100Mbps, full-duplex, lpa 0xC3E1
Feb  1 12:15:20 jchlaptop kernel: [32959.112000] ADDRCONF(NETDEV_CHANGE): eth0: link becomes ready
Feb  1 12:15:22 jchlaptop avahi-daemon[5400]: Registering new address record for fe80::20b:5dff:fe79:914b on eth0.*.
Feb  1 12:15:31 jchlaptop kernel: [32969.408000] eth0: no IPv6 routers present
Feb  1 12:17:01 jchlaptop /USR/SBIN/CRON[11299]: (root) CMD (   cd / && run-parts --report /etc/cron.hourly)
Feb  1 12:21:50 jchlaptop dhclient: DHCPDISCOVER on eth0 to 255.255.255.255 port 67 interval 7
Feb  1 12:21:50 jchlaptop dhclient: DHCPOFFER from 10.32...
Feb  1 12:21:50 jchlaptop dhclient: DHCPREQUEST on eth0 to 255.255.255.255 port 67
Feb  1 12:21:50 jchlaptop dhclient: DHCPACK from 10.32...
Feb  1 12:21:50 jchlaptop avahi-autoipd(eth0)[9087]: Got SIGTERM, quitting.
Feb  1 12:21:50 jchlaptop avahi-autoipd(eth0)[9087]: Callout STOP, address 169.254.5.236 on interface eth0
Feb  1 12:21:50 jchlaptop avahi-daemon[5400]: Withdrawing address record for 169.254.5.236 on eth0.
Feb  1 12:21:50 jchlaptop avahi-daemon[5400]: Leaving mDNS multicast group on interface eth0.IPv4 with address 169.254.5.236.
Feb  1 12:21:50 jchlaptop avahi-daemon[5400]: Interface eth0.IPv4 no longer relevant for mDNS.
Feb  1 12:21:50 jchlaptop avahi-autoipd(eth0)[9088]: client: RTNETLINK answers: No such process
Feb  1 12:21:50 jchlaptop avahi-daemon[5400]: Joining mDNS multicast group on interface eth0.IPv4 with address 10.32...
Feb  1 12:21:50 jchlaptop avahi-daemon[5400]: New relevant interface eth0.IPv4 for mDNS.
Feb  1 12:21:50 jchlaptop avahi-daemon[5400]: Registering new address record for 10.32... on eth0.IPv4.
Feb  1 12:21:50 jchlaptop avahi-daemon[5400]: Withdrawing address record for 10.32... on eth0.
Feb  1 12:21:50 jchlaptop avahi-daemon[5400]: Leaving mDNS multicast group on interface eth0.IPv4 with address 10.32...
Feb  1 12:21:50 jchlaptop avahi-daemon[5400]: Interface eth0.IPv4 no longer relevant for mDNS.
Feb  1 12:21:50 jchlaptop avahi-daemon[5400]: Joining mDNS multicast group on interface eth0.IPv4 with address 10.32...
Feb  1 12:21:50 jchlaptop avahi-daemon[5400]: New relevant interface eth0.IPv4 for mDNS.
Feb  1 12:21:50 jchlaptop avahi-daemon[5400]: Registering new address record for 10.32... on eth0.IPv4.
Feb  1 12:21:50 jchlaptop dhclient: bound to 10.32... -- renewal in 16898 seconds.