Comment 62 for bug 10239

Wow. A 6+ year old bug in basic network connectivity. My home router runs DD-WRT with DNSMasq enabled which "...is designed to provide DNS and, optionally, DHCP, to a small network. It can serve the names of local machines which are not in the global DNS."

But DNSMasq was unable to resolve a hostname for my Ubuntu 10.10 machine, thus other machines failed to locate it. This broke BackupPC for me as it could never resolve the hostname and gave errors like this:
"Error: Can't find IP address for [myHostname]
[myHostname] is a DHCP host, and I don't know its IP address. I checked the netbios name of [myIP_Address], and found that that machine is not [myHostname].
Until I see [myHostname] at a particular DHCP address, you can only start this request from the client machine itself."

I checked /etc/dhcp3/dhclient.conf and it already contained:
send host-name "<hostname>";

However, as mentioned in comment #47, adding the following after that line made it work for me:
send fqdn.server-update on

Now my router knows my hostname and I can ping it (by hostname) from other machines.