How to change the mysql root password

I have installed MySQL server 5 on redhat linux. I can't login as root so I can't change the root password.

mysql -u root -p  
Enter password:  <blank>
ERROR 1045 (28000): Access denied for user 'root'@'localhost'
(using password: NO)

When I try to set one like this:

mysqladmin -u root password 'newpass'

I get an error:

mysqladmin: connect to server at 'localhost' failed
error: 'Access denied for user 'root'@'localhost' 
(using password: NO)'

As if there is a root password set.

I have also tried resetting the password using (described here)

/sbin/service mysqld start --skip-grant-tables

And then making:

mysql> UPDATE mysql.user SET Password=PASSWORD('newpass')     
->  WHERE User='root';  
ERROR 1142 (42000): UPDATE command denied to user ''@'localhost' for table 'user'

I even uninstalled mysql-server (using yum) and then reinstalled it but that did not help.

How do I force reset the root password?