This problem bugged me all week.
Running Windows 2008 Server 32-bit in a Hyper-V VM, suddenly I couldn’t connect via RDP to the server from Windows7-64-bit or Windows Server 2008 32-bit. I could connect via RDP from an older Windows Server 2003 32-bit.
Enough googling and I found this article, and the key was in the “Configuring authentication and encryption”. I basically lowered to the lowest levels of security and it started working. Security Layer changed to “RDP Security Layer” and Encryption Level set to “Low”. When I have time to go explore more I will try and increase these and see what works.