Não haverá uma resposta correta e fixa para o seu problema ou sintoma. A resolução será específica para o seu ambiente.
Quando encontrei esses problemas, essas são algumas das coisas que tento, e geralmente aponta para o caminho certo:
Você tentou sua senha anterior? Pode não ter sido atualizado para novas senhas.
Onde a senha é armazenada? NIS, LDAP, máquina local. .
Existe algum servidor NIS "escravo" que não tenha sido atualizado para o conteúdo mais recente do servidor NIS "Mestre"?
Depois de mudar para o root, você pode voltar para o seu usuário?
Com chave pública copiada e privada disponível localmente, o que "ssh -vvv $ HOST" mostra?
E se você tentar o ssh do host remoto para si mesmo?
EDIT, Em resposta ao comentário abaixo:
(1) Você tentou sua senha anterior?
(2) Quando eu disse "Depois de mudar para o root, você pode voltar para o seu usuário?", Parece que você simplesmente saiu do shell do sudo. O que eu quis dizer foi: Na sua atual shell, "sudo -i" funciona; Depois disso, o trabalho "su $ USER" ou "su - $ USER" será executado; Ou irá falhar com "$ USER não encontrado" ou "Home Directory não encontrado"?
(3) Qual é a saída de "id $ USER"?
(4) Quais são as permissões do seu diretório home & ~ / .ssh /?
(5) Você pode criar outra conta local e login, com alterações na senha? Ou o problema é apenas com sua conta atual?
(6) A sua conta está listada corretamente em / etc / passwd?
(7) O shell de lista está sendo iniciado corretamente quando você tenta executá-lo manualmente?
FINAL EDIT (depois que OP encontrou seu próprio problema):
Se cada novo usuário puder fazer o login, mas após a alteração da senha, o login mostrará "Permissão negada" e, em seguida, verificará o que exatamente está mudando, em / etc / passwd & / etc / shadow.
Crie uma nova conta, faça backups de / etc / passwd & / etc / shadow, login, alterar passwd, logout, comparar os arquivos para ver o que foi alterado e interpretar as diferenças.
No caso atual, verifica-se que "idade da senha" é o problema, em que "a senha foi alterada antes de poder ser alterada por política".