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:

Remote Desktop Connection

The remote computer requires Network Level Authentication, which your computer does not support. For assistance, contact your system administrator or technical support.

NLA support requires the following on your computer:

1. Windows XP Service Pack 3
2. The latest version of the RDC: Remote Desktop client v7.0, although the 6.1 update will also work.
3. The component which takes care of NLA, called Credential Security Support Provider (CredSSP) is not enabled by default on SP3.

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.