Unable to login to mysql as root user access denied

Just got a new server from theplanet webhost

Could not login to mysql as root user

Kept getting messages access denied for user 'root'@'localhost'
using password yes

I tried with and without the password for root user

I then tried instructions for resetting the mysql root user password from
mysql website


Nothing worked!

Finally what I did was:
Stopped mysql
/etc/rc.d/init.d/mysqld stop

Deleted everything from /var/lib/mysql
so the default database 'mysql' was removed

Then reinstalled mysql and mysql-server from yum

yum reinstall mysql
yum reinstall mysql-server

Then started the mysql server again
/etc/rc.d/init.d/mysqld start

This time the startup automatically created
brand new 'mysql' database.

This time I was able to login to mysql with as root user and without a password:
/usr/bin/mysql -u root

Once Logged in I changed password:
mysql> UPDATE mysql.user SET Password = PASSWORD('newpwd')
-> WHERE User = 'root';
mysql> FLUSH PRIVILEGES;

Done!