We just setup some new Windows 2008 R2 servers and we are unable to Remote Desktop into them from our Windows 7 desktops. Remote desktop connects, but after we provide credentials we get:

The connection cannot be completed because the remote computer that was reached is not the one you specified. This could be caused by an outdated entry in the DNS cache. Try using the IP address of the computer instead of the name.

If we connect from Windows 7 to a machine not running Windows 2008 R2, or from a machine not running Windows 7 to the Windows 2008 R2 server, it works fine. Likewise if we connect to the Windows 2008 R2 server from Windows 7 via the IP address then it works fine (although that causes other problems later).

I've only found one other mention of someone having this problem, so I don't think it is just our network.

Any suggestions on how to connect from Windows 7 to Windows 2008 R2 via DNS? Both are 64-bit.

Update: Turns out it does not need to be R2 to get the error. We have another server that is Windows 2008 R1 64-bit that also fails.