Is this a voice mail only solution where Unity/Exchange/DC/GC is all on-box? If not, are you able to launch Active Directory Users and Computers (ADUC) from any of the other domain controllers within the environment, or even from the Exchange server?

Google had a few hits with this error, one solution was to login to the server with a different domain admin account as the account was corrupted that they were trying to use.

Hope that helps,

Brad