We ran into similar problems on the hosting side; another surprise can be the debian-sys-maint password configure by the Debian mysql-server package.