I am in the process of deploying a AD domain based on Windows 2008 R2. All of our clients are Windows 7. In our default domain policy we've enabled password complexity. While we as Admins can set initial passwords for the users that meet complexity requirements, we find that when users attempt to change theirs to passwords that do meet the requirements, the password is rejected. For example, if I attempt to change my password to L11soXtC it is rejected. This password meets 3 of the 5 classifications and does not have 3 or more consecutive characters from my current password (the first one I've had in the domain.) Oddly enough some user's password changes are being accepted, but we can't really ask them what they are. Interestingly enough, we then changed the domain policy to disable complexity requirements, pushed the new policy to a client, and still cannot change the domain password to the one above! So now I am a total loss to explain whether this is occurring at the client level (whether it's Win 7 or 2008 R2 server) or the DC level, but I do know the DCs are not logging anything regarding these password change failures. Anyone have any ideas on how to go about troubleshooting this? I've supported the use of complexity in 2003 R2 domains with XP and some Win 7 clients at another company and never run into issues.

We found the answer on our own. Turns out the "minimum password age" was causing the issue. We had this set to 30 days and assumed that if Admins changed the password the user could change it again (without having to set "user must change password on next logon.") It seems that the minimum password age is still enforced in this case.