Having upgraded our AD to 2003 and installed two new DCs, users can no longer change their passwords. When they try they just get the following message: "Your password must be at least 6 characters, cannot repeat any of your previous 5 passwords and must be at least 21 days old. Please type a different password. Type a password which meets these requirements in both text boxes." The problem is that the password doesn't meet the requirements. What's going on? They were before.
The default password policy for a Windows 2003 domain is different. If you do not want the default password policy then you must reset it in the Password Policy section of the Default Domain Group Policy (you can access this from the Administrative Tools program on the domain controller). The policy must replicate to all DCs in the domain before the users will be able to use the new policy.
However, I would ask you to review your password policy needs. A more restrictive password policy can protect your systems from compromise by preventing the use of easy to guess or easy to hack passwords. For a discussion on secure passwords see the article Selecting Secure Passwords.
More information from SearchWindowsSecurity.com
Expert how-to: Creating strong passwords
Checklist: Hardening user passwords
Tip: The difference between hackers and crackers