Error Creating User Profile Connection - Unable to process Create Message

I have managed to setup User Profile Synchronisation in a few different environments without any problem - Connection created, FIM services are running, user profiles are imported successfully. 

Recently I was trying to setup a new server farm in the production environment.  I followed the exact same procedure as I always do, but this time I am getting a new error message when I tried to create a new User Profile Connection - Unable to process Create Message:

And I was getting these errors in the error log:

Microsoft.ResourceManagement.Service: System.InvalidOperationException: Retrieve schema failed

   at Microsoft.ResourceManagement.ActionProcessor.SyncConfigActionProcessor.Create(String typeName, IList`1 createParameters, Guid creator, Guid cause)

   at Microsoft.ResourceManagement.ActionProcessor.SyncConfigActionProcessor.ProcessInputRequest(RequestType request)

   at Microsoft.ResourceManagement.ActionProcessor.ActionDispatcher.ProcessInputRequest(RequestType request)

   at Microsoft.ResourceManagement.WebServices.RequestDispatcher.ExecuteAction(RequestType request)

   at Microsoft.ResourceManagement.WebServices.RequestDispatcher.ExecuteAction[ResponseBodyType](RequestType request)

   at Microsoft.ResourceManagement.WebServices.RequestDispatcher.DispatchRequest[ResponseBodyType](RequestType request, Guid requestIdentifier, Object redispatchSingleInstanceKey)

   at Microsoft.ResourceManagement.WebServices.RequestDispatcher.DispatchRequest[ResponseBodyType](RequestType request)

   at Microsoft.ResourceManagement.WebServices.ResourceManagementService.Create(Message request)

This is weird because I followed the exactly same procedure as the other environments.  FIM services are running, service accounts are setup properly, Net Bios Name flag enabled for the UPS, what was going wrong? Someone got the same error as me here and they fixed the problem by pointing the Sync to a Windows 2008 Domain Controller:
http://social.technet.microsoft.com/Forums/en-US/sharepoint2010setup/thread/6c68c067-5b2a-482f-925b-5a0a25759344

However I have confirmed both the domain controller of production environment and other environments Windows 2003.  So what was wrong?  I spent 2 overnights, and one premium support called was raised and I was still going no where, where I was 4 days away from the production launch. 

I didn't install the August cumulative updates due to an error I posted earlier (link).  Then I thought....well, worth a try as I have tried out every thing already.  And you know what? That fixed the problem! And this also fixed the August CU problem that I had earlier (it broke the User Profile Service Application). 

So if you are getting this error when you create an user profile synchronisation connection, here are the two things that you should do:

1. Check your domain controller
2. Install the August (or later) Cumulative Updates