If you have a W2K Domain Controller, than it's going to be running DNS. Check the Forward Lookup Zone for your domain and make sure that all the workstations have host (A) records. Although from your second post I'm willing to bet that they're going to be there. Hmm.

Are you using any kind of roaming profiles or offline files? Folder redirection?