Parar o MySQL:

# /etc/init.d/mysql stop
Ou:
# killall mysqld

Iniciar o serviço com o comando:

# mysqld_safe --skip-grant-tables &

Acessar o banco:

# mysql -u root

Executar os comando abaixo:

mysql> use mysql;
mysql> update user set password=PASSWORD("NEW-ROOT-PASSWORD") where User='root';
mysql> flush privileges;

Se quiser redefinir as permissões para login como root, execute:

mysql> grant all privileges on *.* to 'root'@'%';
mysql> grant all privileges on *.* to 'root'@'localhost';
mysql> grant all privileges on *.* to 'root@localhost';

Finalizando com:

mysql> SHOW GRANTS FOR 'root'@'%';
mysql> FLUSH PRIVILEGES;

Parar novamente o MySQL:

# /etc/init.d/mysql stop
Ou:
# killall mysqld

Iniciar e testar:

# /etc/init.d/mysql start