Several things here:
1) Do you have a domain setup correctly? Are the workstations configured to log into the domain/workgroup(for Win9x)?
2) Do you have WINS installed on the server? Verify by checking services for Windows INternet Name Service. YOu must use WINS for NT and pre-Windows2000 workstations.
3) Be sure clients are configured to use/accept WINS. Be sure clients are pointing to WINS server within TCP/IP properties.
4) Test for #3 is can you ping server by name from workstations?5) If nothing else works, do an lmhost lookup and hardcode the IP address and name within lmhosts. Enable lmhosts through IP protocol settings checkbox.
6) If this is a WINS server, then be sure it's pointing to itself within the WINS properties under "primary" and "secondary". Do this only if this is a WINS server. If not, then be sure new server is pointing to the primary WINS server on the network at least.
The above fixes 95% of my problems with NT server connectivity.