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.