Network name no longer available?

On to windows 2000 pro stations, when I select a server I get the following message

Network name no longer available.

If I ping the ip address i get a response.If I ping by machine name I get a response. I’m abale to browse all other machine. I’ took the machine that is giving problems off the domain and then rejoined the domain, still the same problem.If I use Net use to create a mapping to that server I get an error 67.

I also changed the network card on the machine. Anybody have a suggestion?