It's worth mentioning that one other thing I tried after my first post and before your response was removing two of the Avahi daemons (avahi-autoipd, I think, and avahi-daemon). Various forum posts seemed to suggest people had problems where it interfered with dhclient operation, but for me, removing it made no obvious difference...
Lower-case dhcp search, just in case!
It's worth mentioning that one other thing I tried after my first post and before your response was removing two of the Avahi daemons (avahi-autoipd, I think, and avahi-daemon). Various forum posts seemed to suggest people had problems where it interfered with dhclient operation, but for me, removing it made no obvious difference...