When I updated my Windows 2008 R2 Servers to SP1 via Remote Desktop I lost my RDP session when the machines reboot (which is normal). But after they are up and running again, when I try to connect via Remote Desktop, they cancel my connection.

After some research I found that this happens if you install the Security Hotfix 2667402 before SP1. From the KB, under the “Known Issues” section:

After you install security update 2667402 on a computer that is running Windows 7 or Windows Server 2008 R2, and then you install Service Pack 1 (SP1) for Windows 7 or for Windows Server 2008 R2, the binary version of Rdpcorekmts.dll is 6.1.7600.16952 and not 6.1.7601.17767. In this scenario, you may be unable to create a remote desktop session to control the Windows 7-based or Windows Server 2008 R2-based computer.

This issue occurs because the SP1 binary version of Rdpcorekmts.dll was not originally deployed when security update 2667402 was originally installed.

On June 12, 2012, security update 2667402 was rereleased to address this issue. Customers who are running Windows 7 or Windows Server 2008 R2 should install the reoffered update. This includes those who already successfully installed the update that was originally offered on March 13, 2012.

So what I had to do: Access the servers via ILO, uninstall Hotfix 2667402 and re-install it. Then I could access the servers again via RDP.