Paramos el servidor:

sudo service mysql stop

Arrancamos “mysqld_safe”:

sudo mysqld_safe --skip-grant-tables

Dejamos esa consola con “mysqld_safe” corriendo. Abramos otra consola y hagamos lo siguiente:

sudo mysql -u root

Una vez adentro de mysql tiramos los siguientes comandos:

use mysql;
update user set password=PASSWORD("NUEVACLAVE") where User='root';
flush privileges;
quit

Ahora que hemos vuelto a la consola de linux, paramos mysql:

sudo service mysql stop

El anterior comando va a terminar el proceso “mysqld_safe” que habíamos arrancado en la primer consola, por lo que podemos cerrarla.
Listo, arrancamos mysql normalmente y ya podemos usar la nueva clave.