Останавливаем 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:
   fg
   "Ctrl+c"

Запускаем MySQL в обычном режиме.
   /etc/init.d/mysql start