Para resetar a sua senha do MySQL primeiramente você deve encerrar a execução usando o comando:

sudo /etc/init.d/mysqld stop
ou
sudo service mysql stop

Após ter parado execute a seguinte linha de comando:

sudo mysqld_safe --skip-grant-tables &

Agora que iniciou o MySQL, digite:

sudo mysql

Já logado no MySQL, digite:

use mysql;

Agora vamos resetar a senha:

UPDATE mysql.user SET Password=PASSWORD('NOVA SENHA') WHERE User='root';

Agora atualize os privilegios, digite:

flush privileges;

E agora pode sair do MySQL e reiniciar o serviço:

\q
sudo /etc/init.d/mysqld restart;