Windows 7: Trust relationship failed?

Alright so I have a couple of Windows 7 machines on a domain, and I am trying to add users as local admins so that they can tinker with settings without bothering me or the other Network Admin every time they need to install a font or plugin. When I try to add their domain login to the administrators group on the local machine, I get an error.
"Trust relationship between this workstation and the primary domain failed."
Only option is to click Ok.
Not sure why this is happening, found a hotfix from Microsoft, but they claim it is experimental, and an "official update" should be along sometime in the future. Don't like the experimental hotfix approach, anyone know how to fix this, and what might be causing it in the first place?