Provisioning Layer Initialization Failed: ‘Failed To Reconnect To Active Directory Server. Make Sure The Server Is Available And That You Have Used The Correct Credentials.

I came across this strange error while installing Exchange 2010 SP2 on a brand new server running Windows 2008 R2 SP1.