Using Remote Desktop to connect from Windows 8.1 (with a Microsoft account) to Windows 8.1 (with a local account) I encountered the following error (even though the username and password were correct):
Your credentials did not work
The solution is simply to specify localaccount before the username:
After that I was able to connect without any issues. Conversely I experienced no issues using remote desktop from the local account machine to the Microsoft account machine.