Issue

Trying to login to Windows 8 Pro computer via Windows 7 Remote Desktop client using Microsoft Account credentials.
When supplying credentials manually, everything works fine and login is successful. However, if you choose to save the credentials and next time try to login using saved details, login fails with one of the following errors:

Your credentials did not work
The credentials that were used to connect to <IP Address> did not work.
Please enter new credentials.

The specified user name does not exist. Verify the user name and try logging in again. If the problem continues, contact your system administrator or technical support.

Resolution

Provide user name in format MicrosoftAccount\<username>
Where <username> is your Microsoft Account login name
i.e. MicrosoftAccount\john323@gmail.com

If now you get another error:

Your Credentials did not work
Your system administrator does not allow the use of saved credentials to log on to the remote computer <computer name> because its identity is not fully verified. Please enter new credentials.

Check for solution here