Thanks for the helpful posts!
I also ran into this after moving a database from an older Debian server to a newer Ubuntu one. Since I moved *all* databases, including users, this set the password for debian-sys-maint to the one randomly generated on the old system. I fixed this by copying /etc/mysql/debian.cnf from the old system to the new system, so the passwords once again match.