I have a problem that googling has turned up nothing, except this question on experts exchange which I borrowed most of the text from. :)
When I connect via Remote Desktop to a new Windows 2008 R2 server it takes 20-30s to get past the "Securing Remote Connection" message during the login.
If the password is wrong, it does this every time you attempt a login (ie its not a one time thing). However, after a successful login attempt the following logins to the same server goes faster.
Most servers runs on VMware here, but I don't know if that has anything to do with it.
Do you have access to your local DNS Server? You may have some entries in the local zone for AD servers that no longer exist or have had IP's changed. Last year I removed a DC from the network and it caused a delayed login via RDP.
I agree that this sounds like a DNS issue on your 2008 R2 server. Verify that the correct DNS servers are entered on the 2008 R2 server's TCP properties. Also, as recommended previously, review your DNS server for invalid entries.. specifically look for invalid entries in the _msdcs, _sites, _tcp, etc containers/subcontainers. You can also attempt a local login to rule out network issues though if you determine the issue is only via RDP you can look into TCP auto tuning settings on the clients.
For anyone that searches this, try disabling IPv6 on the Remote Desktop server - we have Server 2008 running as a Remote Desktop server connected to a 2003 domain controller. Disabling IPv6 on the remote desktop server made this go from 20-30 seconds to instant :)
I've seen happen on 2008 R2 machines running on ESX 3.5; sometimes the machine's virtual console would freeze (probably a video driver bug) while the system would remain online, and RDP connections would hang like that.
Next time this happens, you should try to connect to the server's console and see if it's working.
If the video driver bug is not the source of this, than it could be an authentication or RDP problem.
I had the same problem after upgrading from SBS2008 to 2010. After migration and removing the 2008 RDP hangs after every action. I had to search for incorrect records in the DNS and found about 5 entries. After cleanup RDP works again.