Powershell – Can’t access Azure VM via RDP any more

I set up an Windows Server VM on Azure last year and after having not logged in for a couple of months I tried to log in recently and strangely it told me my password was incorrect. I proceeded to reset the password, but that didn't work even though it said it was successful. I also tried the method presented here, but that didn't work either.

To be clear:

• I do have access to the VM via Powershell, but resetting the password has no effect.
• The VM is active and IIS services are responding normally.
• RDP is enabled, the service is responding and the correct port is open.
• Upon connecting and authenticating I get the "Your credentials did not work" message. This is even after supposedly resetting the password (double-checking the username and copy-pasting the password both into the Powershell window to reset and then the connection dialog).
• I tried the machine name as a domain prefix (my-vm\username), as well as prefixing with a dot (.\username), nothing (\username) and the full Azure Profile name (myname.cloudapp.net\username).
• the username is a plain alpha username, nothing curly there.
• The passwords I've tried resetting it to should definitely meet complexity requirements: combining upper and lowercase, numeric and the usual non-alphanumeric characters you find in passwords, all more than 8 characters long. In addition I checked that no part of the username was in the password, and the password was not one that had been used previously (if that makes a difference).

So, what could be causing this? Have I missed anything? Are there any other steps can I try to regain access to this machine? Is the only step now to detach the disk and reattach to a new VM and manually copy everything across (which I'm trying to avoid)?