Eu estava em uma situação semelhante a você OP. Eu tinha uma política de grupo para ativar o RDP. Eu verifiquei se isso estava sendo aplicado e se podia fazer ping no servidor de destino. No gerenciador do servidor de 2012, ele disse "Área de trabalho remota: ativada".
No entanto, após seguir as etapas postadas por sushant (cmd > systempropertiesremote) (que também pode ser acessado por outros métodos, por exemplo, sysdm.cpl), cheguei à guia "Remote" das propriedades do sistema e vi que "Don't allow conexões remotas para este computador "botão de rádio foi selecionado. Esta foi claramente a causa do meu problema e, como esperado, a seleção de "Permitir conexões remotas para este computador" me permitiu entrar no servidor.
Eu também tinha outra instância em que, embora o RDC estivesse habilitado, a porta do firewall não estava aberta. Agora tenho como padrão em qualquer domínio eu gerencio duas políticas, uma para habilitar o RDP e outra para permitir que ele passe pelo firewall.