Try looking in the workstation's System Properties then go into the Computer Name tab. Click the bottom button named "Change..." and make sure that the domain and/or workgroup are correct.
I recently had a problem similar and it was because the Workgroup on the System Settings was incorrect.