I just had the exact same issue. Setting up a XP Pro client to connect to Terminal server.
I did notice that whenever I logged into the admin account on the client it kept asking me to complete the installation of the genuine advantage tool, but I kept clicking cancel. For some reason I could not connect to the terminal server however network was up 100%.
So as a last ditch effort I completed the installation of the genuine advantage tool and hey presto remote desktop connection now connects to the terminal server.
Interesting issue, but on not visiting the physical server, hmmm.... thats a stupid one because sometimes the tool needs user intervention but if you can't connect remotely, all I can say is "good one" MS.
Can't try this myself but try sending an administrative restart from the client. Could be that the WGA hasn't finished installing yet.