If you have a problem changing the password on windows 2008 domain users from
a windows box. It could be group policy problem.
If you have group policy setup, make sure group policy password settings are in the domain controllers default group policy and its enabled. Do not put it in any other GP, like one you attached to an OU. Also set minimum age from 1 To 0. This stops the bogus complexity error you get when you try and change the password, even when you use a super complex password.