Many people get caught out with group policy - I stand up and tell people all about some of the gotchas on a regular basis. You know, things like making sure you understand the double negatives such as Disabling "Do not keep history of recently opened documents" to keep the history. It really is worth reading them very carefully. The point? I myself got caught out this morning and was a bit too thoughtless when changing settings for a new virtual machine domain. I wanted to turn off all the password restrictions to make demonstrations easier. Into GPMC, edit the default domain policy and bounce down to the computer configuration/windows settings/security settings/account policies/password policies.
I changed all the settings with the exception of storing passwords using reversible encryption to "Not Defined". Yet, when I was trying to create a test user account with a simple password, it wouldn't take it. No end of gpupdate/force would do it - checked the event logs and found nothing relating to policy. The point? Check your settings very carefully. To turn off password complexity you need to Disable the "Password must meet complexity requirements" rather than set it to "Not Defined".