Don't ask me how, but the password in the CredVault was wrong, and no one was owning up to changing the master admin password.
So this is what you do.
Start Azure PowerShell, login to your Azure Account.
Get-AzureVM -ServiceName [VMHOSTNAME] -Name [VMHOSTNAME] | Set-AzureVMAccessExtension -UserName userNameHere -Password securePassHere | Update-AzureVM