passwd: Authentication token manipulation error

Question

I am running a Ubuntu 12 machine, and have recently been working to secure it. I made all the changes from this guide. I am not running a Linode, but I used these as a starting point for setting up the firewall and such.

All went smoothly, and I have been using the machine for some time now. I tried to lock some users' accounts, with the passwd -l command, and that was successful. However, when I try to add a new user, or change my password, I have the strangest error:

myuser@mymachine:~$ passwd 
Old Password: 
passwd: Authentication token manipulation error
passwd: password unchanged

Or, when adding a new user:

myuser@mymachine:~$ sudo adduser mynewuser
Adding user `mynewuser' ...
Adding new group `mynewuser' (1011) ...
Adding new user `mynewuser' (1002) with group `mynewuser' ...
Creating home directory `/home/mynewuser' ...
Copying files from `/etc/skel' ...
passwd: Authentication token manipulation error
passwd: password unchanged
Try again? [y/N] 

I searched for this error, and the vast majority of problems were solved by remounting / as read and write. However, this is not the problem, as it is mounted as read and write (I confirmed). Note that the same error is encountered from different users, and from root trying to change other users' passwords.

Do you have any insight as to why I am (seemingly spontaneously) getting this error? I have not done any manual editing of the shadow or passwd files--or really made any change to user authentication at all.

In case it is relevant:

ls -lh /etc/passwd -rw-r--r-- 1 root root 3.2K Jul 23 17:26 /etc/passwd 
ls -lh /etc/shadow -rw------- 1 root shadow 3.1K Jul 23 17:20 /etc/shadow

Solution

This issue occurred due to incorrect permissions set to /usr/bin/passwd.

Please try to set the permissions as 4511.

You can update the permissions using the command:

chmod 4511 /usr/bin/passwd

This will resolve the issue.

Comments

[The_Anomaly]

In case it is relevant: myuser@mymachine:~$ ls -lh /etc/passwd -rw-r--r-- 1 root root 3.2K Jul 23 17:26 /etc/passwd myuser@mymachine:~$ ls -lh /etc/shadow -rw------- 1 root shadow 3.1K Jul 23 17:20 /etc/shadow

[cornelinux]

Did you created the user "myuser" later? He should be in the group "sudo". Take a look at /etc/group.

[Cosmic Ossifrage]

It would be useful if your answer mentioned the purpose of the setuid bit and why (for what purpose) this needs to be set.