Faça o login em um terminal como root e pare o daemon mysql.
/etc/init.d/mysqld stop
Em seguida, inicie o daemon mysql e pule as tabelas de permissões que armazenam as senhas e outras informações privilegiadas
mysqld_safe --skip-grant-tables &
Você deverá ver o mysqld iniciar com sucesso. Agora você deve poder se conectar ao mysql sem uma senha.
mysql --user=root mysql
e, em seguida, atualize as informações relevantes:
update user set Password=PASSWORD('new-password') where user='root';
flush privileges;
exit;
e então reinicie o daemon mysql como você faria normalmente
/etc/init.d/mysqld restart
Veja também a documentação do MySQL para ajudá-lo se você ficar preso