With Windows Vista and newer, when you enable remote desktop for administration, there are options to allow "Old Clients (less secure) [no network level authentication]" and "New clients (more secure) [with network level authentication]".
Is there any way to connect to the "more secure" version from non-microsoft clients? I've tried from the ubuntu client, and it works to connect to XP/2003 but it fails to connect to a Win7 Desktop or 2008R2 server, though I can connect to both of those machines from another Win7 machine.
There is a way now! The FreeRDP project has NLA support, but only in their git repo right now not in a stable version. They've had NLA support since late January if I remember right. The next stable version should have full support, but until then you'll have to compile your own.