I discovered that Macs sometimes send their hostname in the request, and sometimes do not. In particular I found that if the computer name (Control Panel > Sharing -> Computer name) contains a space, then NO hostname will be sent (under OS X 10.6). If it does NOT contain a space, then it WILL be sent.
I compared the DHCP requests using tcpdump, with and without a space in the computer name.
With the computer name `chris-macbook-space`:
11:13:41.939462 IP (tos 0x0, ttl 255, id 36007, offset 0, flags [none], proto UDP (17), length 328)
0.0.0.0.68 > 255.255.255.255.67: BOOTP/DHCP, Request from 00:17:f2:xx:xx:xx, length 300, xid 0x9b57c74c, secs 1, Flags [none]
Client-Ethernet-Address 00:17:f2:xx:xx:xx
Vendor-rfc1048 Extensions
Magic Cookie 0x63825363
DHCP-Message Option 53, length 1: Discover
Parameter-Request Option 55, length 10:
Subnet-Mask, Default-Gateway, Domain-Name-Server, Domain-Name
Option 119, LDAP, Option 252, Netbios-Name-Server
Netbios-Node, Netbios-Scope
MSZ Option 57, length 2: 1500
Client-ID Option 61, length 7: ether 00:17:f2:xx:xx:xx
Lease-Time Option 51, length 4: 7776000
Hostname Option 12, length 19: "chris-macbook-space"
With the computer name `chris-macbook space`:
11:07:13.077664 IP (tos 0x0, ttl 255, id 36003, offset 0, flags [none], proto UDP (17), length 328)
0.0.0.0.68 > 255.255.255.255.67: BOOTP/DHCP, Request from 00:17:f2:xx:xx:xx, length 300, xid 0x432cbbda, secs 2, Flags [none]
Client-Ethernet-Address 00:17:f2:xx:xx:xx
Vendor-rfc1048 Extensions
Magic Cookie 0x63825363
DHCP-Message Option 53, length 1: Discover
Parameter-Request Option 55, length 10:
Subnet-Mask, Default-Gateway, Domain-Name-Server, Domain-Name
Option 119, LDAP, Option 252, Netbios-Name-Server
Netbios-Node, Netbios-Scope
MSZ Option 57, length 2: 1500
Client-ID Option 61, length 7: ether 00:17:f2:xx:xx:xx
Lease-Time Option 51, length 4: 7776000
Note the missing `Hostname Option 12, length 19: "chris-macbook-space"` in the latter case.
So you could try removing spaces and any other special characters from the computer name, to see if that enables it to be resolved on the network.