1. Verify that the system is indeed running TCP/IP and has an IP address. If it doesn't, add one.
2. If it is running any other protocols (IPX/SPX, NetBEUI, etc.), remove them at least for testing -- you can add them back later.
3. Verify if you can ping the system on its IP address. If you can't, verify that you can ping 127.0.0.1 from the server itself. This could be sign that the NIC is bad.
4. Verify that you can ping the system by its fully qualified domain name. If you can't, verify that the name is entered in DNS and WINS.
5. Verify that the server is a member of the same domain that all the rest of the servers and clients are. If it is not, either add it or verify that trust relationships are working properly.
6. Ensure that the server service is running.
7. Finally, make sure that you are logging on to the client system using a network account.
Also, Microsoft has a Q article detailing a more obscure issue related to a corrupted MUP that you may want to review.