Trust Relationship Primary Domain

I have been loosing workstations off of the domain
unable to log in as administrator. I am getting a message ” The trush relationship between this workstation and the primary domain has failed.
The workstations seem to be going down one at a timeI have lost 3 stations over the last 2 days.
Any clues to what is wrong with my server.
The only way to get them back on the domain was to rename them and then I could rejoin the domain.
Any Ideas?

Thanks
Connie