Ever delete or change the password for debian-sys-maint user in Mysql?
Debian/Ubuntu scripts get grumpy if their mysql user goes away or has it's password changed. Happens to me especially often when cloning slaves.
Try this out to fix it:
mysql -uroot -p -vv -e "GRANT ALL PRIVILEGES on *.* TO 'debian-sys-maint'@localhost IDENTIFIED BY '`sudo awk '$1 == "password" {print $3}' /etc/mysql/debian.cnf | head -1`'; FLUSH PRIVILEGES;"