After doing some VirtualBox upgrading and network reconfiguring, the next time I started up my Linux guest (Fedora Release 11), it was not showing up by name on my network.
I reviewed the Fedora network configuration options, and it was set to Automatically obtain IP address settings with [dhcp], and also set to Automatically obtain DNS information from provider. I cleared this one and restarted it and now it shows up by name.