O problema era do driver bluetooth de harmonia CSR recente que eu instalei. Os drivers tentam adicionar alguma autenticação de marca bluetooth que estava causando o problema e o RDP falha, independentemente de uma senha boa ou ruim.
A solução simples é seguir para
C:\Program Files\CSR\CSR Harmony Wireless Software Stack
e altere
BLEtokenCredentialProvider.dll
para
BLEtokenCredentialProvider.dll.BAK
E o problema agora está resolvido para mim.