É muito comum que a senha do usuário root do MySql seja perdida.

Pra modificar a senha é bem simples, basta fazer, como usuário root:

# dpkg-reconfigure mysql-server-5.1

Pronto, irá aparece uma tela pedindo a nova senha de root, observe que usei mysql-server-5.1 pois a versão do meu SGBD é esse, para descobrir a versão faça antes:

# dpkg -l | grep mysql-server-

Tá ai a dica.

Boa sorte.