After two weeks of not being able to connect to my Windows Home Server from my Windows 7 laptop I think I finally tracked down the problem. I'm hoping I can save someone else a few hours (ok, days) trying to fix this issue.
First, the symptoms. At some point, seemingly randomly, my Windows 7 laptop could no longer connect to the Home Server using the machine name. So \\homestorage wouldn't work. Strangely, the IP address, or \\192.168.150.5 would work. Unfortunately, all my drive mappings and the windows home server console itself relied on the hostname. When trying to connect to \\homestorage, I would get a non-helpful error 0x80004005.
I had another Windows 7 machine on the network and it was still able to see the Home Server so I was pretty convinced that this wasn't a network issue or a Home Server issue but something specific to my laptop. To debug it, I checked that all the important services were running: Computer Browser, TCP/IP NetBIOS Helper, RPC, etc. I installed and uninstalled various network protocols including Client for MS Networks. I uninstalled any virtual NICs including VirtualBox. I stopped and started firewalls and virus software. I installed and watched MS NetMon. Finally I learned the wonders of nbtstat.
Using nbtstat -r, I saw that all the values were 0. Nothing was ever resolved by my machine and nothing ever registered. This seemed really strange and I could confirm with the other Win7 machine that it was resolving and registering with the same command. I also found that I could run nbtstat -a 192.168.150.5 and Win7 would find and cache the Home Server name. Using nbtstat -c, I could see the HOMESTORAGE machine name show up with a 600 second countdown. While the name was in cache, I could access the host without error; however once it dropped from the cache, I was back to square one.
Finally, after much comparing between the two Win7 machines, I noticed that the Node Type, listed with ipconfig /all was Hybrid on the working machine but Peer-Peer on my laptop. A little research and I determined that Peer-Peer didn't make sense because I don't have a WINS server on my home network. A little more research and I found out how to change it here:
I edited the registry and set DhcpNodeType to a value of 8 (Hybrid), rebooted, and presto! Now nbtstat -r lists successful resolutions and registrations. I have no idea how the network stack got switched into peer-peer, but thankfully things seem to be working now.