This worked for me. I didn’t have to redo my pc. It’s an old post but it needs reference. I removed .NET 3.5 SP1 and I was able to connect to an XP Pro SP3 machine. I have to give credit to the following post: http://help.lockergnome.com/windows/Connect-Windows-XP-SP3-Remote-Desktop-Connection–ftopict585711.html
I removed .NET Framework 3.5 SP1. .NET 2.0 and 3.0 need to be at service pack 2. They were at 1 and removing 3.5 SP1 still didn’t work. So remove 3.5 SP1 and make sure 2.0 and 3.0 are up to SP2. If not, Windows update.
Once you’re able to remote desktop you can reinstall 3.5 from Microsoft. One more thing, the issue I had was on an Optiplex 960. It was able to connect to another Dell M4400, but not to the other 960 in the office.