After setting up a fresh debian system, I was not able to change or set any passwords on it.
Whatever I tried I got the error messages
passwd: System error passwd: password unchanged
I came across a few people with the same problems and some hints on the debian user list but not an explicite solution. But the hints there and the fact that I got the line
passwd[10717]: pam_winbind(passwd:chauthtok): valid_user: wbcGetpwnam gave WBC_ERR_DOMAIN_NOT_FOUND
told me to look for windows-like things in /etc/pam.d/common-password and there it was the line
password requisite pam_winbind.so
Since I do not connect to any windows domain server I commented out that line and things worked fine after that.