Authentication

I need some help with a problem that I am having at work. There are a few user’s who are running Workstation and are not able to logon. The message that they get when they try to logon is that either their password is wrong or that their computer account doesn’t exist on the PDC. Also when I go to Server Manager and check the properties on their computer, it returns a message saying, the trust relationship on the workstation failed. Does this problem have anything to do with the LMCompatibilityLevel setting and if so, can you offer any suggestions.