Windows XP SP3 and the latest supported Remote Desktop client update should support Network Level Authentication (NLA). But, when connecting to an RDS server with NLA enabled, you may still get the following error:
NLA support requires the following on your computer:
The first two components are usually not an issue, but even with the updates installed, NLA cannot be used because the CredSSP provider is not activated by default, causing the not-so-useful and rather misleading error message to appear.
You can enable CredSSP by downloading and running the Microsoft FixIt 50588 from KB 951608, or perform the steps outlined in the Let me fix it myself section on that page.