Eu resumi minha solução aqui:http://snippets.dzone.com/posts/show/13267
sudo stop mysql
sudo mysqld --skip-grant-tables --skip-networking
mysql
mysql> update mysql.user set password = password('your_new_password') where user = 'root';
mysql> flush privileges;
mysql> exit;
sudo mysqladmin shutdown
sudo start mysql
