Em seu /etc/pam.d/common-password, altere o minimum_uid em sua primeira linha para algo maior que 1000, por exemplo:
password [success=3 default=ignore] pam_krb5.so minimum_uid=10000
Isso funcionou para mim. Isso é o que você deve ver em /var/log/auth.log depois de alterar a senha desse usuário como root:
Dec 26 12:34:36 3.8.0-29-generic passwd[22667]: pam_unix(passwd:chauthtok): password changed for service1