@Andrew Currie
To reproduce the situation you're facing I used the same quickstart template, saved it as a .json on my local machine and used Powershell to deploy and provided credentials at the prompt when asked. Once the machine was running I was able to RDP to the Public IP and I was able to log in using the credentials I set in Powershell.
I want to make sure I'm understanding what you're experiencing. All of the above matches what you did, however when you attempt to provide credentials, you are getting "The logon attempt failed" error message. Once you visit the Azure portal and provide new credentials through Support + troubleshooting > Reset Password, you're finally able to connect is that right?
If so, when you click on "More choices" do you have the option to "Use a different account"? This should let you enter the credentials you set up in the Powershell session.
Please verify that the username and password you're creating in the Powershell session meet the requirements per this doc
Please also make sure you are not copy/pasting your password into Powershell and/or the login screen as this can cause issues as well.
I hope this helps, if not, write back here and we'll work more on getting this sorted.