A quick google showed DNS as a cause - I checked my DNS configuration and it was correct so I discarded this as the reason.
A few member servers were receiving the following error:
Log Name: System
Date: 12/01/2011 11:51:40 AM
Event ID: 1006
Task Category: None
The processing of Group Policy failed. Windows could not authenticate to the Active Directory service on a domain controller. (LDAP Bind function call failed). Look in the details tab for error code and description.
On the details tab I was getting ErrorCode 49.
The following TechNet article from Microsoft says Error Code 49 is the following:
Error code 49 (Invalid credentials)
This error code might indicate that the user's password expired while the user is still logged on the computer.
To correct invalid credentials:
1. Change the user's password.
2. Lock/unlock the workstation.
3. Check if there are any system services running as the user account.
4. Verify the password in service configuration is correct for the user account.
This error code description from Microsoft completely threw me off track diagnosing the computer account passwords, rejoining PC's to the domain and diagnosing the Kerberos Key Distribution Center (KDC) service.
All tests against the domain using nltest for the computer account were passing successfully!
I was confident it was nothing to do with authentication!
There were so many forum posts on the Internet leading to DNS as being the cause for this error. I decided to revisit my name resolution even though DNS was working correctly.
I checked the local host file. It was full of entries.
Removed these entries and the problem was resolved. A very simple fix for such a painful problem.
Hopefully this post will stop others from going through my pain!