Tente verificar a configuração "Autenticação do servidor" RDP nas configurações de conexão RDP do cliente. Eles são os mesmos na máquina que não funciona e a máquina que funciona? Eu estou pensando que o cliente que não funciona está definido para "Não conectar", quando talvez deveria estar em "Warn Me"