This was really annoying. I had setup RDP to connect to a cloud service but I kept getting an error trying to login. I even tried redeploying, changing the password and a load of similar things but no dice.
I then found out, when visiting the remote configuration page on the Azure portal, that the username "administrator" is not allowed to be used for RDP on Azure. This was confusing because this is the default username that Visual Studio gives to RDP when you configure it for the cloud service.
Anyway, I just had to change it to something else and it was fine.