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

# /etc/init.d/mysql stop

Запускаем MySQL с новыми параметрами:

# mysqld_safe --skip-grant-tables &

Соединяемся с MySQL, указываем базу mysql, так как в ней меняем пароль:

# mysql -u root mysql
...
mysql> UPDATE user SET Password=PASSWORD('новый пароль') WHERE User='root';
mysql> FLUSH PRIVILEGES;
mysql> exit

Затем перезапускаем MySQL:

# /etc/init.d/mysql restart