The subject behavior may occur if all of the following are true:

1. The Windows Server 2003 domain controller has the NT4Emulator value enabled.

2. The client is running Microsoft Windows XP Service Pack 1 (SP1).

3. The client types a password that does not comply with the security requirements.

The error should read something like:

Your password must be at least x characters and cannot repeat any of your previous y passwords. Please type a password that meets these requirements in both text boxes.

NOTE: See When a domain user attempts to change their password during logon, they receive 'You do not have permission to change your password'?