Oops... my bad. Sorry for the blank post.
I'm not a total network wiz, but I've been maintaining a small one at work and a small one at home (using a D-Link router to share Roadrunner) for a couple of years now. My home netweork had several problems when first set up (all the computers were running ME at the time and file sharing was erratic). Most of the problems were eventually cured by going to fixed IP adresses. Have you tried fixed IPs??
Anyway, when I started converting some of the comps at home to Win XP Pro, things got a little stickier. I still used fixed IP addresses, but to get computers to show up on a home network I had to make sure they all were members of the same workgroup, and that they all had something set up to share on the computer (otherwise they might not show up on the workgroup list). And, of course, they won't show up if they're not turned on (I believe in WinME they sometimes showed up on the MyNetworkPlaces list even if they weren't turned on.
Then, in WinXP, you still have to drill down through "MyNetworkPlaces/ EntireNetwork/ Microsoft Windows Network" to see the shared computers. They don't necessarily show up under "My Network Places" directly.
So, if you haven't already, make sure all the computers are on the same workgroup, make sure they all have a folder set up to share, and make sure you drill down to the workgroup to see if they are there. By the way, I am using TCP/IP with NetBios set to default under WINS.
Good Luck.