Are these workstations images?
Is the workstation time nearly identical to the server time?
Btw, Trust issues can be client-server too.
As for the Profile issue:
http://support.microsoft.com/default.aspx?kbid=811151
In additioan to the questions, please post a copy of the relating Event log error message.