Comment 36 for bug 10239

dhclient does send the hostname with the patch (I verified via wireshark), but it doesn't send a client identifier (cid). A fritz box (DSL router, market leader in germany) won't update it's dns records with the sent hostname without a cid, and some other DSL routers show this behavior, too, at least from what I gather using google. Maybe the relevant RFCs have something to say about this.

To make dhclient send a cid, you have to manually enter the mac address in /etc/dhcp3/dhclient.conf.

dhcpcd *does* send a cid (and hostname) by default without any patches, as does windows and OS X. In light of bug 26949 perhaps you might consider making dhcpcd the default client?