Remote Desktop works only with old clients

All of our Windows 8.1 computers suddenly refuse Remote Desktop connections.

The problem is when we connect TO Windows 8.1
We don't have the problem when connecting to other Windows versions.

edit: problem solved with the Microsoft update KB2962806. Thanks to Bertrand SCHITS for his answer.

What we found until now:

• we can always connect as a local user. The problem is only for domain users (admin and regular)
• we can connect with old mstsc.exe versions. For example we can connect from Windows 2003 and 2003 R2 computers. We can't connect from Windows 7, Windows 8.1, and Windows 2012 R2.
  If we copy the old mstsc.exe (version 5.2.xxxx) from Windows 2003 to a newer computer, we can connect
• if we connect from an old mstsc.exe version (as stated above), then during several minutes we can connect from whatever version we want. We must use the old version again after a random amount of time (from 30 seconds up to several hours)
• with the recent mstsc.exe versions we sometime can't connect some users, but this works with other users. This behaviour disappear as soon as we use an old version, and can reappear 2 days later
• (thanks to Warren's answer) if we manually add enablecredsspsupport:i:0 into the .rdp file, the credentials are not asked before connection (so the behaviour is the same as with old clients), and we can connect with whatever client version. But we can not auto-connect, and the login process involve each time to choose to logon as another user (even if it is the same user)
• (thanks to Pathum Anjana) we applied the optional update KB2830477 on both sides of the connections

What we tested:

• we tested from local network to local, and from distant to local. No difference
• we disabled the firewall
• we tested disabling every security features with gpedit.msc Computer Configuration > Administrative Templates > Windows Components > Remote Desktop Services > Remote Desktop Session Host > Security
• we enabled auditing for logon events, and nothing into the logs. Nothing obvious into other logs (how to enable RDP protocol logs?)
• we tested on one computer located on another network (the domains are not related), which has only 7-zip installed. No printer drivers, no Group Policies, nothing else. It is only a fresh Windows 8.1 up to date. We have exactly the same problem
• we asked Google, and he said "I really don't know". He now direct us to this page, which is a very good answer but not really helpfull
• we removed every updates until february 25 (several days before the problem occured). No improvement, so the problem could be an existing setting set up to a different value by a recent update (and not reverted back when the update is removed, which is probably the usual behaviour)

When we can't connect, the error message is exactly the same as the one we get with a wrong password (but no entry into the security log):

• every computer has valid licences
• we use MSE as anti-virus
• some Windows 8.1 are preinstalled by the manufacturer (Lenovo), while others are installed by us. The only common factor I see is the fact we manage all of them

Any idea about what we can do to troubleshout this ?