Você não deve excluir o certificado auto-assinado para que o Windows use o certificado gerado pela CA. É possível que o Windows também precise desse certificado auto-assinado para outras coisas não relacionadas ao RDP.
Qual política de grupo você está usando para gerar o certificado? São as políticas de inscrição automática? Você verificou que o certificado cuja impressão digital você está referenciando realmente existe no sistema de destino no armazenamento do computador local?
Se estivesse funcionando há um mês e não agora, o certificado poderia ter sido renovado? Em caso afirmativo, teria um novo valor de impressão digital.
Se o certificado correto estiver lá, verifique também se ele possui uma chave privada válida. Haveria um pequeno ícone de chave no topo do ícone normal do certificado no snap-in Certificados. Também diria que na janela de detalhes do certificado é semelhante a esta imagem: