First off, have you followed up on the suggestions/observations in the error messages?
Reference to duplicate named machines for example, and clicking on the link to microsoft (which will pass them the data in the error message. Some of these can be quite helpful.
Other things I’ve seen which can cause this sort of thing are where on of the machines has been either turned off for a few weeks, or has just been restored from an older backup image.
Related to this is that there is an encrypted password between machines in a domain (NT4 onward) which is changed automatically every so often. If it gets out of sync with the domain controller, then it will be considered invalid.
Hope that helps,