This was a new one, we put in some sonicwalls and so by default no one would have access to the internetz until they authenticated. The unintended consequence is a slow RDP connection because it can’t verify the certs

Solution is http://codermike.blogspot.com/2011/05/delayed-rdp-connections-in-windows-2008.html

i.e.

You can also disable NLA or CredSSP in the 6.1.x client by creating a .rdp file and adding the following property:
enablecredsspsupport:i:0
Setting the following group policy fixed the issue:

Set the following setting to Enabled: Turn off Automatic Root Certificates Update