Changing NT User Passwords

My users need to change their Domain passwords every 45 days. When they respond to the prompt to change the password or type Ctrl-Alt-Del, they encounter a dialogue box explaining that they do not have the rights to change their password. I am not imposing policies.