Can't change passwords

I have a win2000 server (w/ service pack 2) and win2000 pro workstations (some w/ sp 1, some w/ sp 2). The server is a PDC (the only server on the network). The user accounts are set to "must change password at next logon". When a user logs on tothe domain, they get the 'password has expired' message and are brough to the change password screen. They type in a new password and get a 'system cannot change your password...domain IMS is not available". If I change the account not to expire the password, they can logon and run the login script, no problem. Any suggestions on what to try?