I'm attempting to include as many keywords as possible, so hopefully, should someone get themselves into the same situation I did, they will find this and be able to fix it!
Installed some Windows 2003 (SP2) servers - did the SP2 install remotely, with only VPN access. Discovered that despite "Remote Desktop" being enabled for administration, I was not able to log in remotely from my XP box - however, SOME servers in the same environment (remote, at the same facility) worked.
Turned out that on the suspect ones, the Windows Firewall / Internet Connection Sharing service was not started. Starting this service, or going into firewall configuration (control panel), clicking yes to start the service and disabling firewall is all that is required. Doh.