Server 2008 Complex Password ?

I have a odd question or maybe just a skew understanding of the topic,
I moved over to new 2008 servers, enabling complex password the GPO.
All users have the same default password to login, with a force to change the password on first login.
Now when they press ctrl-alt-del and choose the change password option,
they get a ‘password does not meet complexity requirements by domain’ error.
I’ve checked the GPO setting on the server and workstation, the GPO settings are the same, but why can’t the user change the password ?
Any help / ideas / suggestions will be much appreciated !