"The Trust relationship between this workstation and the primary domain failed"

Hi all-

I've come upon a rather peculiar issue @ my workplace today.  The symptoms have been around for about 2 weeks now but today is the first time I was able to kind of get an idea of what's really happening.

I've got a WinNT 4.0 server in my work enviornment that's supported by a 3rd party.  This server is accessed by lots (30-40) of users in my Department.  The server resides on the 6th floor of a rather large building on campus and user's are spread all over.  To further complicate matters, there are 2 major networking groups on campus.  1 controls the clinical areas and the other controls the school areas.

Now on to the problem...  A few weeks back a few users noted issues logging into this WinNT 4.0 server from their Windows 95 machines.  These machines are older and kind of prone to being annoying, so I didn't think too much of it.  The network around here has been known to not allow logins for a while and then 15 minutes later it's working fine.  Anywho, these folks kept getting told that their domain was not available for authentication and so they could not login to the server and map the drives needed for an app they use.  The Win2000 machines in this area which had been joined to this domain some time ago all were working fine and had no issues at all, so I guessed it was just the Win95 machines having issues.  

Today I replaced one of the Win95 machines with a freshly reimaged Win2000 machine and was unable to join it to the domain from my office.  My office is on the "other" network (school) and the server is on the "clinical" network, so I thought maybe it was just some odd routing issue, so I went to another room down the hall that did have the clinical network installed and tried to join the machine to the domain there.  Still no dice.  The domain could not be found and the error message told me it might be a DNS issue.  

I knew the quick fix was to wheel the machine up to the 6th floor, join it on the same network as the server and be done with it, so that's what I did.  After I joined the machine with no problems I logged in as myself (into the domain as opposed to my local machine account) and that worked fine.  I took down the machine and wheeled it back downstairs and installed it at the location where it's replacing the 95 PC.   I logged into the domain as me no problem (I thought) and was able to manually map drives on the server with no issue.  I then went to "User's and Passwords" and attempted to add other user's to the domain so that they could log into the machine with Power User permissions.  I was then informed that "The user could not be added because the following error has occured:  The Trust relationship between this workstation and the primary domain failed."  

Now, in the past, the only thing I've needed to do to successfully point folks to this server is to add the server's IP address to the clients WINS settings and then all's well.  I could join machines to the server no problem, authenticate to the machine no problem...all worked fine.  Now, the WINS settings are there, I can ping the WinNT 4.0 server and Tracert to it, but cannot log into the machine on a Win95 machine or Join users to the domain on Win2000 machines that are already joined to the domain.  I did test this on the machines that have been seemingly fine, and since they had been joined some time ago, they seem to be functioning OK, but are also unable to add users to the machines.  

I'm guessing this issue is either server side or some sort of odd networking issue since machines can be joined while on the same network switch as the server.  Since I'm not NT server guru though I'm not sure how to approach resolving the problem and this 3rd party may be more prone to punt this off as a networking issue regardless of it's true origin.

Any thoughts or suggestions greatly appreciated.

Lee