Remote Desktop works only with old clients

Maybe this is related to KB2962806. You should try to apply it.
I don't know how to apply this update because it is not available on the Microsoft site. I only get it with the automatic Windows update but not on every computers.

This update solved a similar problem for me. And since this update is applyed on SOME computers, every others work too. I didn't searched why.

Credential prompt has been driving me mad for the past couple of days, and following the chain of recent events leads me to believe it's related to KB3035017 that our 2012 RDP servers installed recently.

After searching this post and other I've come across something that so far is working around the problem.

Testing RDP icons side my side on the same machine yields credentials prompt error one one, and successful login on the other.

http://www.boredsysadmin.com/2008/06/how-to-disable-credentials-prompt-of.html

Hope this helps others, I'll continue to monitor and search for a correct fix.

Cheers