Make sure the clock on the client is within a few minutes (3 mins I think) of the server, because Kerberos authentication depends on it.
Also, you can try removing the machine records. Take the clients machines out of the domain (set the to a some bogus etmp workgroup) then open Workgroup Manager and go to Accounts / Machines / Windows clients and delete the clients from the list (and click Save). Then go back to the clients and try to join the domain.