Останавливаем MySql Server
sudo /etc/init.d/mysql stop
Запускаем mysqld для конфигурации
sudo mysqld --skip-grant-tables &
Логинимся под рутом
mysql -u root mysql
Устанавливаем новый пароль
UPDATE user SET Password=PASSWORD('НовыйПароль') WHERE User='root'; FLUSH PRIVILEGES; exit;