Ok, acho que descobri. Indo para o /etc/pam.d/* eu habilitei opções de depuração e auditoria para a maioria dos arquivos comuns- *. Isso não ajudou muito além de me apontar para o módulo pam_unix:
passwd[45463]: pam_unix(passwd:chauthtok): username [root] obtained
passwd[45463]: pam_unix(passwd:chauthtok): username [root] obtained
passwd[45463]: pam_unix(passwd:chauthtok): password - new password not obtained
Eu comecei a examinar mais de perto cada uma das opções da senha comum dada ao pam_unix.so. As opções que eu tinha eram: obscuro use_authtok try_first_pass sha512
Lendo a página man do pam_unix , vi que o use_authtok estava relacionado à alteração da senha. E falou sobre usá-lo depois do pam_cracklib. No meu caso não há pam_cracklib então decidi tentar remover essa opção. Isso restaurou totalmente a funcionalidade do comando passwd.
Não tenho certeza se um script adicionou essa opção ou se era um padrão.
Obrigado por todos aqueles que tentaram fornecer ideias.