Server 2003 password change

Problem:
We have a network running a file server with windows 2000 and a Windows 2003 server with Exchange 2003.
The 2000 box doesn't have active directory installed anymore, all user authentication i handled by the win 2003 box.
We have a mixture of win 98 and xp machines.
Some of the win 98 machines are unable to change their passwords.
We have already installed the win 2003 client on the 98 boxes.
The strange thing is, if We go to the server and change the password, it works.
If we go to the server and check the box "user must change password at next logon", the users are able to change their passwords. Right after that, if they try to change it, it will not let them.
THERE ARE NO PASSWORD POLICY RESTRICTIONS IN PLACE!
This must be some kind of registry key or something still hanging around that we cannot find.
any ideas?

Is this only on the Windows 98 boxes, or on the XP ones also.

It only happens on the 98 machines.
I installed the active directory client on them, tried rejoining the domain.
Everything else is fine, users just cannot change passwords.

How are they trying to change their passwords?

They have tried at logon screen and in "passwords" in control panel. They only time they are able to change them is if I go to the server and check "user must change password at next logon".

I dont really remeber there being a way for Win 98 users to change their domain password from their workstations. Give me a little bit to look into this.