Today's discovery is that Debian isn't smart enough to include its own hostname when sending a DHCP request. The only workaround is to edit dhclient.conf and manually hardcode the computer's hostname. Then restart "networking" and hope the DHCP client actually does come back up (it didn't when I had to do this earlier today, leaving me with a box that didn't want to speak to anything).
For added hilarity, look at Debian bug 151820 (and yes, that was first raised nearly 10 years ago).
Interestingly, on that mini-network the only devices which didn't require funky non-obvious configuration to make DHCP and hostnames work (the setup is such that the DHCP server updates DNS as devices come and go) were some of the SIP phones and a Windows 2000 server.