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.