A área de trabalho remota funciona apenas com clientes antigos

Todos os nossos computadores Windows 8.1 de repente recusam conexões de Área de Trabalho Remota.

O problema é quando nos conectamos ao Windows 8.1
Não temos o problema ao conectar a outras versões do Windows.

edit: problema resolvido com a atualização KB2962806 da Microsoft. Obrigado a Bertrand SCHITS por sua resposta.

O que encontramos até agora:

• sempre podemos nos conectar como um usuário local. O problema é apenas para usuários do domínio (admin e regular)
• podemos nos conectar com versões antigas do mstsc.exe. Por exemplo, podemos nos conectar de computadores com Windows 2003 e 2003 R2. Não podemos nos conectar do Windows 7, Windows 8.1 e Windows 2012 R2.
  Se copiarmos o antigo mstsc.exe (versão 5.2.xxxx) do Windows 2003 para um computador mais novo, podemos conectar
• se nos conectarmos a partir de uma versão antiga do mstsc.exe (conforme indicado acima), durante alguns minutos podemos nos conectar a partir de qualquer versão que desejarmos. Devemos usar a versão antiga novamente após um período de tempo aleatório (de 30 segundos até várias horas)
• com as versões recentes do mstsc.exe, às vezes não conseguimos conectar alguns usuários, mas isso funciona com outros usuários. Esse comportamento desaparece assim que usamos uma versão antiga e pode reaparecer 2 dias depois
• (graças à resposta de Warren) se adicionarmos manualmente enablecredsspsupport:i:0no arquivo .rdp, as credenciais não serão solicitadas antes da conexão (portanto, o comportamento é o mesmo dos clientes antigos) e podemos nos conectar com qualquer versão do cliente. Mas não podemos nos conectar automaticamente, e o processo de login envolve a cada vez escolher fazer logon como outro usuário (mesmo que seja o mesmo usuário)
• (graças a Pathum Anjana) aplicamos a atualização opcional KB2830477 em ambos os lados das conexões

O que testamos:

• testamos de rede local para local e de distante para local. Nenhuma diferença
• desativamos o firewall
• testamos a desativação de todos os recursos de segurança com gpedit.mscComputer Configuration > Administrative Templates > Windows Components > Remote Desktop Services > Remote Desktop Session Host > Security
• ativamos a auditoria de eventos de logon e nada nos logs. Nada óbvio em outros logs (como habilitar os logs do protocolo RDP?)
• testamos em um computador localizado em outra rede (os domínios não são relacionados), que possui apenas o 7-zip instalado. Nenhum driver de impressora, nenhuma política de grupo, nada mais. É apenas um novo Windows 8.1 atualizado. Temos exatamente o mesmo problema
• perguntamos ao Google e ele disse "eu realmente não sei". Ele agora nos direciona para esta página, que é uma resposta muito boa, mas não muito útil
• removemos todas as atualizações até 25 de fevereiro (vários dias antes do problema ocorrer). Nenhuma melhoria, então o problema pode ser uma configuração existente definida para um valor diferente por uma atualização recente (e não revertida quando a atualização é removida, o que provavelmente é o comportamento usual)

Quando não conseguimos conectar, a mensagem de erro é exatamente a mesma que recebemos com uma senha errada (mas sem entrada no log de segurança):

• todo computador tem licenças válidas
• usamos MSE como antivírus
• alguns Windows 8.1 são pré-instalados pelo fabricante (Lenovo), enquanto outros são instalados por nós. O único fator comum que vejo é o fato de gerenciarmos todos eles

Alguma ideia sobre o que podemos fazer para solucionar isso?