Had the same problem, but really needed the dhcp server properly resolve the hostname as I intend to have multiple Yuns on my home network. My home router is running DNSmasq which is set to respond to both dhcp and dns requests.
Turns out linino needs one more config setting to have the hostname be part of the dhcp request. Edit /etc/config/network and add the following under the "config interface 'lan'" section:
option hostname "arduino"
You can change the hostname to whatever you want, but make it match the name you have given your Yun in the "Yun Board Configuration" page (default is "arduino").
Reboot your Yun and it should now show up with a nice name in the list of dchp clients on your router.