Issue
Setup encountered a problem while validating the state of Active Directory: Active Directory operation failed on Machinename.domain.com. The supplied credential for ‘domain\administrator’ is invalid.
Resolution
From command prompt,
Run control keymgr.dll and from Credential manager, delete Credentials matching with Exchange server name. There are three category, “Windows Credentials” “Certificate-based credentials” and “Generic Credentials”
In my case, I deleted all the parameters under all three category and restarted Uninstallation setup and uninstalled successfully