I summarised my solution here: 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