O RDP requer que a porta 3389 esteja aberta para TCP (e UDP, bem como para redirecionamento de áudio / vídeo). O RDP ainda funcionará se apenas o TCP estiver acessível.
--- este bit não está totalmente correto, mas ainda assim é útil, e eu não quero modificar completamente a resposta ---
O fato de você poder fazer telnet para 3389 significa que o TCP está aberto, mas não necessariamente o UDP.
Eu tive um problema um pouco semelhante, e descobri que o UDP não estava aberto devido a um problema de firewall (estou ciente de que você declarou que não há firewall instalado, mas vamos ver se ele está aberto ou não). Tente usar o PortQry e veja se ele é OUVINDO nessa porta para TCP e UDP. netstat -a na máquina problemática também pode ajudar aqui.
--- fim ---
Verifique também se existem usuários com acesso à Área de Trabalho Remota (se você vir SIDs em vez do nome de usuário real, o usuário provavelmente não existe), se são válidos e se as senhas foram definidas - Iniciar - > Painel de controle - > Ferramentas Administrativas - > Gerenciamento de computadores - > Usuários e grupos locais na árvore - > Grupos - > Usuários da Área de Trabalho Remota.
Por fim, verifique também se o grupo Usuários da área de trabalho remota pode se conectar remotamente. - Iniciar - > Painel de controle - > Ferramentas Administrativas - > Política de segurança local - > Políticas locais na árvore - > Atribuição de direitos de usuário - > Permitir logon pelos serviços de terminal na lista à direita.
EDITAR: A resposta modificada está correta, de acordo com todos os comentários listados abaixo. Obrigado pessoal.