This error can be caused at least by two reasons.
1) New password does not meet password policy requirements in Active Directory.
Solution: provide new password which meets the requirements.
2) User has recently changed his password successfully and you have non zero value in "Minimum password age" parameter in Local Security Policy\Security Settings\Account Policies\Password Policy section.
Solution: set "Minimum password age" parameter to 0.