Changing password policy in active directory 2003

I am attempting to change our orginizations password policy but I have a few questions. Currently all users have extremly weak passwords that are easily rembered by their peers. I would like to implimint a password policy using group policy to do this. But if I change the group policy setting to require strong passwords and my users attempt to log on with their old passwords will they still be able to? I need to give classes to my users to help them understand the need for strong passwords/passphrases and will do this one dept at a time. My theory would be to set the gpo for strong passwords min 8 char and maintian a history of those passwords for 5 times. Then go dept by dept and select the user must change password at next log in but I can't do this if gpo will not allow people to log on with their old passwords. Thanks in advance. I cdould put a test lab together and test this but since I do not have a test lab ready to roll and this has become an urgent need because of some firings I need to find out asap. Thanks.