This message was deleted.

Only thing that comes into my mind is that you need LDAPS (Secure LDAP) to change the password.

Are you using a primary and secondary auth? If so make sure you're sending the correct credential index to the SF

I would check that Kerberos Change/Set password ports TCP/UDP 464 are open between your storefront server and domain controllers. I got process on my blog you can double check https://c4rm0.wordpress.com/netscaler-allow-user-ad-password-changes/

Yep it's all SSL for auth, single LDAP auth only. We took a packet trace in the end and could see that the NS was sending a blank password to StoreFront after the password was changed, for some reason my lab setup with the same build behaved properly. The client has updated the firmware to the latest build and it's resolved the problem.