What authentication methods are permitted in sshd_config on your host?
I find that if I enable only ChallengeResponseAuthentication, passwd
doesn't work, but if I enable PasswordAuthentication it does.
Thats what we discovered, gentoo's opensshd installation had passsword auth method disabled by default