Domain User Can Not Change Password

Ran into a weird password issue on my test domain running Windows 2008 R2 with function level set to Windows 2008 R2. The symptom is all users are not able to change their password. The error prompt is the new password does not meet complexity requirement. The real cause to this issue is not password complexity. It is caused by the fact that by default, no domain group policy is enabled on domain, not even Default Domain Group Policy which is already linked to the domain. Can't remember what the default setting was on older domains, but this seems to be the case for me on two and all test domains running Windows 2008 R2.