Ok I think I have it figured out. Digging into /etc/pam.d/* I enabled debug and audit options for most common-* files. That did not help much other than to point me toward the pam_unix module:
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
I started looking more closely at each of the options in common-password given to the pam_unix.so. The options I had were: obscure use_authtok try_first_pass sha512
Reading the man page for pam_unix I saw that use_authtok was related to changing the password. And it talked about using it after pam_cracklib. In my case there is no pam_cracklib so I decided to try and remove that option. That restored the passwd command's functionality fully.
I am not sure if a script had added that option or it was a default.
Thanks for all those who tried to provide ideas.