What protocol are you using? A protocol is the langauge that the machines are going to talk to each other using - they all must speak a common language.
I'll assume that you're using TCP/IP.
How are the machines connected together at the physical layer? Connections though a hub or switch function differently then a router.
I'll assume that you're using a switch.
Try dropping to the DOS command line and doing a "PING" command to the other machine's TCP/IP address. A sucessful reply means that the protocol stack and hardware are fine and the problem lies with the Windows software (see above suggestion about workgroups). A failure means that typically you've got a hardware issue or the device driver for the Network Interface Card(NIC) is bad or not loaded. Get another copy or an update.
With a TCP/IP workgroup each machine should be able to ping the others in the group.
Look at the TCP/IP subnet mask as they should all be the same within your network - this is a common problem too.