Active Directory will not allow passwords to be updated unless the LDAP communication is encrypted.
The standard method of encrypted LDAP communication is TLS/SSL. To make the AD TLS/SSL capable a certificate must be generated. If you have a CA the the following needs to be done:
At the end run a gpupdate.
Pre Windows 2012:
- Got to Start->Programs->Administrative Tools->Domain Security Policy.
- Go to Security Settings->Public Key Policies->Automatic Certificate Request Settings , right click and select New Automatic Certificate Request.
- Select Domain Controller from the window, then select your CA.
If you do not have a CA the following article might be useful: http://support.microsoft.com/kb/321051