This is a known error message for IT Administrators. But I'll highlight the options that are available to mitigate this issue.
You will face this issue when you try to connect into,
Azure virtual Server
Windows 2012 Server
Windows 2008/20008 R2 Server
First, you need to check whether your enter you Admin credentials on the same RDP window is working. This would be working.
Then run the MTSC without Admin (mstsc /admin) and give your user credentials.
If that is an Azure VPC, without clicking the Connect tab on the VM control page, you can copy the Virtual machine IP address or the FQDN and use the normal RDP connection to connect.
In Azure, you can find the VPC details under Essentials tab.
Hope this will help.