krb5-lib gives false error while changing password "Requested protocol version not supported" in case of failover

Issue

In environment with two MS active directory servers (Windows 2008 R2) working in failover and RHEL5 client authenticating against them, when one of AD
servers goes down, changing password through kpasswd/passwd fails with (wrong) error.

-sh-3.2$ passwd
Changing password for user wuser2.
Kerberos 5 Password:
New UNIX password:
Retype new UNIX password:
passwd: Authentication token manipulation error

$ kpasswd
Password for wuser1@EXAMPLE.COM:
Enter new password:
Enter it again:
requested protocol version not supported changing password.