Primeiramente devemos para o serviço mysqld

killall mysqld

Após, inicie novamente o serviço mas em modo seguro,

safe_mysqld --skip-grant-tables &

Ou

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

Ou

mysqld_safe --skip-grant-tables &

Agora se conecte ao mysql usando o cliente mysql,

mysql
Ou
/usr/bin/mysql

Após se conectar, vamos acessar o banco mysql,

use mysql;

Agora vamos alterar a senha de root,

update user set password = password('nova_senha_aqui') where user='root' and host='localhost'; 

Após recarregue os privilégios,

flush privileges;

Pronto, agora saia do mysql,

quit

Vamos sair do modo seguro,

/etc/init.d/mysql stop

Vamos iniciar o serviço normal,

/etc/init.d/mysql start

E vamos conectar no MySQL,

mysql -u root -p

Era isto,

[]'s
Guilherme