Could be our old friend a broken Winsock.
Winsock Fix
Happens to me regularly when changing Networking hardware or most recently adding a Belkin Serial/USB adapter. What seems to happen is that the DHCP'ing by the Router is destroyed and the PCs/Laptops give themselves IP addresses outside of the Workgroup range.
Download it
HERE or Google for it yourself.
Got me out of hole many times.
On each PC try "ipconfig" in a command prompt window. You'll soon see whether the IP addresses are the problem.