After much fooling around and some reading, I discovered in the middle of some document a statement that the DHCP server keeps track of whether it thinks it has updated the DNS server, to avoid one round trip when renewing a lease. This means that if the DHCP server thinks it has updated DNS, it won't try again and if the DNS server doesn't have that address, it'll never get it.
Well, the DNS server will never get it until you do the following on the DHCP client machine to force a release of the lease:
sudo dhclient -rOnce you do that and then renew the lease again (e.g. disconnect and connect the network) everything is fine.