Password Policy Error

I am getting an error stating the password on a new user (most new users, but not all error) does not meet my password policy. But it does. I am absolutely positive of that. I have a minimum 8 chars, password complexity, and history enabled. But I have tried passwords 10 chars long with chars from all 4 of the groups. It is a new user, so history shold not be an issue.

I recently added a 64 bit 2003 domain controller while the remaining DCs are 32 bit. I do not think this shold matter, but thought it worth mentioning.

Ideas?