Not that I have pinpointed the exact problem, but like I mentioned earlier that I have constant on and off again networking issues. Sometimes one pc or another just doesn't see eachother and vice versa. And after reading this thread again I played with mine half the friggin' day trying to find the cause, because the pc I'm on right now would not see the other pc's. I could surf the net, all network settings were dead on, yada, yada.
And just like his issue, the other pc's could see and access this one just fine.
Just now I unplugged the router power, let it set a second or two, plugged it back in..... linked right up with the other pc's just fine.
So maybe he needs to look at the router side of things. (just an idea)
BTW - I have a Linksys WRT54G router.
EDIT: Just noticed it took a reboot and a little time for everything to show up on each computer correctly. So there may be a time delay depending on if one of the PC's has been elected as the master browser server and it's waiting for basically a ping from each of the pc's type thing. (or something to that effect)