O FreeRDP (um spin-off do rdesktop) suporta isso em versões recentes.
Existe uma maneira de usar o rdesktop ou outro cliente Linux para se conectar a um servidor que exija autenticação no nível da rede?
No Windows Server 2008 R2 - Painel de Controle - Sistema e Segurança - Sistema - Permitir Acesso Remoto, há uma opção que diz "Permitir conexões apenas de computadores que executam a Área de Trabalho Remota com Autenticação no Nível da Rede". Então, com isso ativado, eu não consigo conectar do Linux. Eu posso conectar-me a partir do XP, mas você precisa do SP3 e tive que editar algumas coisas no registro para que ele funcione.
Infelizmente, eu não sei se você vai ter muita sorte. Eu tive que desabilitar o NLA para fazer com que nossos clientes linux se conectassem quando eu estava configurando isso há um ano, pois não encontrei nenhum suporte para ele no linux
Olhando no sourceforge para o rdesktop, vejo uma solicitação de recurso que ainda está aberta e algumas postagens de 2009 com pessoas pedindo suporte.
Remmina que parece ser baseado em FreeRDP, negocia as configurações certas (para mim, conectando-me a uma máquina com Windows 7 que requer NLA) fora da caixa.
O rdesktop v1.7.0 tem várias correções (provavelmente a mesma versão recente do FreeRDP) para problemas de compatibilidade do RDP 6.0 / RDP 6.1 (Windows 7/2008).
Veja o changelog: link
Mas o NLA (Network Level Authentication) ainda não é suportado.
Quanto ao FreeRDP, somente as notas de lançamento da v0.7.1 mencionam isso na seção "trabalho em andamento": "A autenticação no nível da rede está concluída no meio do caminho (o TLS funciona, mas a autenticação NTLM é parcialmente implementada)"
As notas de lançamento das versões seguintes nem sequer mencionam. Assim, provavelmente ainda está no mesmo estado "meio caminho feito".