Is there a way to use rdesktop or another Linux client to connect to a server that requires Network Level Authentication?
From Windows Server 2008 R2 -- Control Panel -- System And Security -- System -- Allow Remote Access there is an option that says "Allow connections only from computers running Remote Desktop with Network Level Authentication". So with this enabled I can con not connect from Linux. I can connect from XP but you need SP3 and I had to edit a couple of things in the registry for it to work.
FreeRDP (a spin-off from rdesktop) supports this in recent versions.
Sadly, I dont know if you are going to have much luck. I had to disable NLA to get our linux thinclients to connect when I was setting this up a year ago as I could not find any support for it in linux
Looking on sourceforge for rdesktop I see a feature request for it that is still open and some posts from 2009 with people asking for support.
http://sourceforge.net/tracker/index.php?func=detail&aid=1773895&group_id=24366&atid=381350
Remmina which appears to be FreeRDP-based, negotiates the right settings (for me, connecting to a Windows 7 machine which requires NLA) out of the box.
rdesktop v1.7.0 has various fixes (probably the same as the recent FreeRDP version) for RDP 6.0 / RDP 6.1 (Windows 7 / 2008) compatibility problems.
See the changelog: http://sourceforge.net/projects/rdesktop/files/rdesktop/1.7.0/
But NLA (Network Level Authentication) is still not supported.
As for FreeRDP, only the release notes of v0.7.1 mentions it in the "work in progress" section: "Network Level Authentication is half-way done (TLS works, but NTLM authentication is partially implemented)"
Release notes of the following versions do not even mention it. Thus it's probably still in the same "half-way done" state.