We had the same problem on our home network - one roommate could see everyone else's computer but no one else could see his, not even the host computer, and we were all running XP Pro. I tried everything that every MS Knowledge Base arcticle recommended and then some, to no avail. Everyone could still access the internet, so it wasn't that big a deal, but still...WHY?
I finally realized that he was the only one running XP with SP2[/I], and the rest of us hadn't bothered to upgrade yet. One of the big deals about SP2 is the supposed improvements in security. And his computer was the only one being really pushy about making you keep that Personal Firewall on, and MS swears that you can still share files and folders and all that, but when I turned off his firewall, he suddenly stopped being the Invisible Computer. When I turned it back on, the cloaking device had been activated once again. So I think that was the problem - but I didn't check any further than that so I could be wrong. I'd be interested to know if you have the same scenario...?