Pessoal recentemente tive esse problema e achei que era problema na VPS na qual cheguei a enviar até ticket de suporte para a empresa de host, mais o problema não era na VPS e sim em uma atualização de maio de 2018 feita pelo windows update.

Imagem do alerta que impedia de acessar a VPS:



Causa
Devido à diferença na versão do provedor de autenticação (CredSSP) que pode ser usado para cada cliente e servidor do Remote Desktop.

Em relação à vulnerabilidade de área de trabalho remota, teve mudanças nas seguintes atualizações do Windows Update :

Atualização CredSSP lançada no Windows Update em março de 2018 CVE-2018-0886
(No entanto, o uso da versão antiga é liberado com a permissão padrão)
No Windows Update desde maio de 2018, versão reforçada usada no CredSSP (versão antiga truncada)
(O valor padrão de Criptografia Oracle Remediation foi alterado de Vulnerável para Reduzir)
Como eu utilizo o windows10 a solução que encontrei para isso foi abrir o prompt do DOS como administrador e executar o seguinte comando:
Código:
REG ADD HKLM\Software\Microsoft\Windows\CurrentVersion\Policies\System\CredSSP\Parameters\ /v AllowEncryptionOracle /t REG_DWORD /d 2
Feito isso você irar conseguir acessar seu VPS normalmente.