reset mysql root password on ubuntu
Here is a more secure way to reset password without skip-grant-tables
Suppose you want root to have myn3wp@ssw0rd as the password
Step 01 : Create a script to execute when mysqld first start up
Create a file called /var/lib/mysql/init-file.sql with these two lines
GRANT ALL PRIVILEGES ON *.* to root@localhost
IDENTIFIED BY 'myn3wp@ssw0rd' WITH GRANT OPTION;

Step 02 : Run these three(3) lines in the OS
chown mysql:mysql /var/lib/mysql/init-file.sql
service mysql restart --init-file=/var/lib/mysql/init-file.sql
rm -f /var/lib/mysql/init-file.sql

Step 03 : THERE IS NO STEP 03. YOU ARE DONE !!!
Give it a Try !!!
CAVEAT

I used to recommend two restarts of mysql that required editing my.cnf
I learned a better approach from @ShlomiNoach
This answer improves on it more by not editing my.cnf at all

UPDATE 2013-06-17 07:05 EDT
OK Since mysqld for Ubuntu does not like init-file on the command, you must edit the my.cnf. Please do these next two steps
STEP 01) Add these lines to my.cnf under the [mysqld] group header
[mysqld]
init-file=/var/lib/mysql/init-file.sql

STEP 02) Allow mysql to read files from /etc/mysql
sudo vim /etc/apparmor.d/usr.sbin.mysqld

Add the line:
/etc/mysql/*.sql r,

STEP 03) Restart MySQL
This should work for you. Give it a Try !!!