Tente isso. Apenas pressione Ctrl + Alt + T no seu teclado para abrir o Terminal. Quando se abre, execute o (s) comando (s) abaixo:
sudo mysql -u root -p
Isso solicitará uma nova senha. Se isso não funcionar tente:
sudo /etc/init.d/mysql stop
sudo mysqld --skip-grant-tables &
mysql -u root mysql
UPDATE user SET Password=PASSWORD('New_Password') WHERE User='root'; FLUSH PRIVILEGES; exit;
Fonte: MySQL RM