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 !!!

I have dealt with this issue before.

When you ran

select count(1) UserTableColumnCount from information_schema.columns
where table_schema='mysql' and table_name='user';

you should have gotten 42. That's how many columns MySQL 5.5 has for mysql.user. Since you got 39, that means you must have upgraded from MySQL 5.1. That has 39 columns.

I wrote an earlier post about the number of columns in mysql.user in different versions : MySQL service stops after trying to grant privileges to a user

Here is the post where I dealt with this : mysql: Restore All privileges to admin user

Hopefully you could run

# mysql_upgrade --upgrade-system-tables

to realign mysql.user and have it autofill missing permissions with Y.

Give it a Try !!!

If you want to try to fix the mysql.user manually, here are the steps:

#
# Backup the mysql.user table
#
CREATE TABLE mysql.user_backup LIKE mysql.user;
INSERT INTO mysql.user_backup SELECT * FROM mysql.user;
#
# Add Missing Columns
#
ALTER TABLE mysql.user 
    ADD COLUMN Create_tablespace_priv enum('N','Y') NOT NULL DEFAULT 'N'
    AFTER Trigger_Priv
;
ALTER TABLE mysql.user ADD COLUMN plugin char(64);
ALTER TABLE mysql.user ADD COLUMN authentication_string text DEFAULT NULL;
#
# Give root user all privileges
#
UPDATE mysql.user SET
Select_priv='Y',Insert_priv='Y',Update_priv='Y',Delete_priv='Y',
Create_priv='Y',Drop_priv='Y',Reload_priv='Y',Shutdown_priv='Y',
Process_priv='Y',File_priv='Y',Grant_priv='Y',References_priv='Y',
Index_priv='Y',Alter_priv='Y',Show_db_priv='Y',Super_priv='Y',
Create_tmp_table_priv='Y',Lock_tables_priv='Y',Execute_priv='Y',
Repl_slave_priv='Y',Repl_client_priv='Y',Create_view_priv='Y',
Show_view_priv='Y',Create_routine_priv='Y',Alter_routine_priv='Y',
Create_user_priv='Y',Event_priv='Y',Trigger_priv='Y',
Create_tablespace_priv='Y'
WHERE user='root';
FLUSH PRIVILEGES;

That's it !!!