Останавливаем MySQL:

/etc/init.d/mysql stop

Запускаем в режиме без проверки прав доступа:

/usr/bin/mysqld_safe --skip-grant-tables &

Соединяемся как root без пароля:

mysql --user=root mysql

Обновляем пароль:

mysql> update user set Password=PASSWORD('новый пароль') WHERE User='root';
mysql> flush privileges;

Завершаем работу mysqld_safe:

"Ctrl+c"
killall mysqld

Запускаем MySQL в обычном режиме.

/etc/init.d/mysql start