Permission denied after changing password (password is correct)

Question

I'm currently trying to configure a system where the initial install was done by someone else.

I could ssh into the box, and while on it, added some groups to me account and changed my password (I still have that session open, and have root access via sudo -i). I was told "passwd: all authentication tokens updated successfully.". However on attempting a second connection I get "permission denied".

I have reset the password again (typing very carefully) and tried to login again (typing very carefully). But still the same.

The account is not locked (at least usermod -U has no impact and there is no '!' in the shadow file). I am not attempting to login as root. There is no /etc/nogin

My shell has not been changed from /bin/bash

So I could still access the machine, I copied over my public key to ~/.ssh/authorized_keys. Attempting to login using that bumps me to the password prompt - which continues to fail.

This is a RHEL 6.5 box

The audit log (selinux mode is permissive) seems to be pointing towards the password failing:

type=USER_AUTH msg=audit(1455985417.050:170881): user pid=23682 uid=0 auid=0 ses=1548 subj=unconfined_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=PAM:authentication acct="user" exe="/usr/sbin/sshd" hostname=192.168.1.81 addr=192.168.1.81 terminal=ssh res=failed'
type=SYSCALL msg=audit(1455985417.051:170882): arch=c000003e syscall=2 success=yes exit=4 a0=7fdafebb7e30 a1=401 a2=7fdafebb2366 a3=0 items=1 ppid=28418 pid=23682 auid=0 uid=0 gid=0 euid=0 suid=0 fsuid=0 egid=0 sgid=0 fsgid=0 tty=(none) ses=1548 comm="sshd" exe="/usr/sbin/sshd" subj=unconfined_u:system_r:sshd_t:s0-s0:c0.c1023 key="session"
type=CWD msg=audit(1455985417.051:170882):  cwd="/"
type=PATH msg=audit(1455985417.051:170882): item=0 name="/var/log/btmp" inode=41 dev=fd:05 mode=0100600 ouid=0 ogid=22 rdev=00:00 obj=system_u:object_r:faillog_t:s0 nametype=NORMAL
type=USER_AUTH msg=audit(1455985417.052:170883): user pid=23682 uid=0 auid=0 ses=1548 subj=unconfined_u:system_r:sshd_t:s0-s0:c0.c1023 msg='op=password acct="(unknown)" exe="/usr/sbin/sshd" hostname=? addr=192.168.1.81 terminal=ssh res=failed'

Answer 1

There is going to be no one fixed correct answer to your problem or symptom. Resolution will be specific to your environment.

When I encountered such issues, these are some of the things I try , and it usually points to the right way :
Did you try your previous password ? It might not have got updated to newer passwords.
Where is the password stored ? NIS, LDAP, local machine . . .
Is there any "slave" NIS server which has not got updated to latest content from "Master" NIS server ?
After switching to root, can you switch back to your user ?
With public key copied over and private available locally, what does "ssh -vvv $HOST" show ?
What if you try ssh from remote host to itself ?

EDIT , In response to below comment:
(1) Did you try your previous password ?
(2) When I said "After switching to root, can you switch back to your user ?", it seems you simply exited from sudo shell. What I meant was : In your current shell, "sudo -i" works ; After that, will "su $USER" or "su - $USER" work ; Or Will it fail with "$USER not found" or "Home Directory not found" ?
(3) What is the output of "id $USER" ?
(4) What are the permissions of your home Directory & ~/.ssh/ ?
(5) Can you create another local account and login , with changes in password ? Or is the problem only with your current account ?
(6) Is your account listed correctly in /etc/passwd ?
(7) Is the list shell starting correctly when you try to manually execute it ?

FINAL EDIT ( after OP found his own issue ) :
If every new user can login, but after password change, login shows "Permission Denied", then check what what exacctly is changing, in /etc/passwd & /etc/shadow.
Create a new account, take backups of /etc/passwd & /etc/shadow, login, change passwd, logout, compare the files to see what has changed, and interpret the Differences.
In current case, it turns out that "password age" is the issue, wherein "password was changed before it was allowed to change by policy".

Answer 2

The cause of the problem was that the policy required a minimum age of 7 days on any password - my account with a "default" password had been created less than 7 days previously (but then why was it possible for me to change it using passwd without reporting any issue?).

I had gone through the pam configuration in some details but completely omitted to look at /etc/login.defs (and still think that there's a defect in passwd allowing me to change the password when the minimum period had not expired).