O problema é causado pelo UAC no Windows 7 / Windows Vista. Como o cliente RDC não tem, por padrão, permissão para criar uma nova chave na ramificação HKLM \ Software \ Microsoft, ela não pode reconstruir as informações de licenciamento depois de excluídas! Isso causa uma falha silenciosa com a mensagem de erro "problema no protocolo de licenciamento". (Idealmente, o programa seria reprojetado para exibir um prompt de desafio do UAC nessa situação).
Para corrigir isso, basta executar o RDC como administrador quando você se reconectar ao computador de destino pela primeira vez. Isso permitirá que a permissão do cliente RDC reconstrua as chaves de registro necessárias. Você só precisa fazer isso uma vez.