authentication - Ubuntu Server - User account unable to change password

I am running an instance of Ubuntu Server 12.04 LTS.

I recently set it up and began adding user accounts to the server. One of the users can login to the server normally vis public key, however when he tries to change his password with passwd he gets Authentication token manipulation error. And when trying to run sudo commands, the user receives the error Authentication failure when using the temp password created.

The user has been granted access to all privileges of sudo. ALL = (ALL) ALL

I have tried both logging on through my terminal and suing into the user and running the passwd and sudo commands, and they authenticate just fine, I can not figure out what is having a problem with authentication.

Answer

check if your /etc/shadow file is not protected with some attribs.

lsattr /etc/shadow

if this is the problem remove
using :
chattr -[attr] / etc/shadow

this file contain the passwords of all system users encrypted and when you try to change your password. the system try to override this file, may be.

chattr -[attr] / etc/shadow

you should be root for this actions, good luck