First I would check the cable with a cable tester (providing you have one)
Then check to see that each PC has the same protocols enabled. For example, just tcp/ip on each (if its a winders box). I noticed that having netBIOS and IPX can screw things up.
Also make sure that they are on the same subnet. I have had weird issues with that cropping up. Theoretically, if one is on a wrong subnet (to what is wanted), neither shall talk, but windows is wierd to begin with ;D