First thing to check would obviously be to check whether the desired password really matches the policy. While you shouldn't see the "NMAS:cryptographic service failure" part in this case it's still possible.
Next you might want to let the user login to iManager and try to change his password from there. If that works you're likely facing a pure client-side issue such has messed-up nici and / or nmas binaries or invalid rights on the user's nici directory.