So you know at least that it is not a wireless issue.
Two possibilities, at first glance:
1. If you are using blank or empty passwords on any of the machines, assign real passwords to all users.
2. It sounds like a "Browser War" might be going on. If you look in Control Panel, Administrative Tools, you might see several entries complaining about some computer attemptig to become the Master Browser.
Forum member Bob Linn writes:
"How do I know I have a browser problem
When you open My Network Places, the computer list you see is obtaining from the master browser of your network. You have a master browser issue if you have the following symptoms. 1) If you can ping a computer name, you can search it, you can map it, but that computer doesn't show or take long time to show up on My Network Places.
2) Net view command shows no lists or shows "System error 6118 has occurred. The list of servers for this workgroup is not currently available".
3) when clicking on Computers Near Me in My Network Places or workgroup name in Entire Network, the following error message may appear: "Cannot Access 'Computers Near Me' " or "Workgroup is not accessible" errors.
4) when click workgroup name under Entire Network Places, you get "Workgroup is not accessible. You might not have permission to use this network resource. Contact the administrator of this server to find out if you have access permission. The list server for this workgroup is not currently available.""
If you see a lot of entries in the error log of the troublesome computer relating to the Master Browser, disable the ability of the computer to assert a Master Browser role. Mr. Linn notes further:
"Change master browser in w2k or XP:
Go to Program files, Admin tools, services then in the right panel right click on computer browser and right click go to properties then from the startup list select Disabled. Or type regedt32, and scroll to this key change value to False
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\Browser\Parameters IsDomainMaster=FALSE
"
Source:
