Seu certificado não está importando corretamente (para que esteja associado à sua chave privada), ou está no lugar errado ou não é o tipo certo de certificado.
Se você estiver instalando corretamente as propriedades lhe dirão que está associado a ela, você também verá a sobreposição de chave no ícone cert indicando a mesma coisa. Se você não está vendo isso, não vai funcionar.
No que diz respeito à localização, deve estar no armazenamento de Certificados Pessoais da máquina e não do usuário. A maneira correta de importá-lo para que ele fique no lugar certo é abrir o MMC como administrador, adicionar o plug-in de certificados e selecione a opção para usar a conta de computador. Em seguida, selecione a loja pessoal, clique com o botão direito, Todas as tarefas e, em seguida, importe a partir daí.
No entanto, parece-me mais provável que o certificado não tenha o valor OID de uso de chave estendido correto na lista EKU. Para que um certificado seja usado para o RDP, ele deve ter a Autenticação do Servidor (1.3.6.1.5.5.7.3.1) em algum lugar da lista. Isso é mencionado como o OID necessário neste artigo do Technet que expande o requisitos para certificados TS com um pouco mais de detalhe.
Há também uma chance de que você tenha problemas se o nome do servidor não corresponder ao nome do certificado - não consigo encontrar nada que diga que eles devem corresponder, mas não me surpreenderia se fosse necessário.