I had this error when I moved all database server files, phisically, from one server to another for replication purposes and used the mysql startup script. The new server is a Debian Squeeze, in debian there is a user debian-sys-maint to do maintenance tasks, to avoid this error with the mysql startup script you have to create this user in your new database server.
The password for this user can be seen in this file:
# cat /etc/mysql/debian.cnf
# Automatically generated for Debian scripts. DO NOT TOUCH!
[client]
host = localhost
user = debian-sys-maint
password = password
socket = /var/run/mysqld/mysqld.sock
[mysql_upgrade]
host = localhost
user = debian-sys-maint
password = password
socket = /var/run/mysqld/mysqld.sock
basedir = /usr
To create the user, log in as mysql root user and run this statement:
GRANT ALL PRIVILEGES ON *.* TO 'debian-sys-maint'@'localhost' IDENTIFIED BY 'password';
In my case, the original server was a Centos 5.5, so that the user debian-sys-maint did not exist, but in case the server was another Debian you can use the same statement to only reset the user password.