Fatal error: Can't open and lock privilege tables: Table 'mysql.host' doesn't exist

I am on a server that has afresh install on RHEL 5. I was able to install Apache and PHP just fine., but I am having serious trouble with my MySQL installation. I tried the following:

yum install mysql-server mysql 

And didn't get any errors or conflicts. Then I tried to start mysql with the following commands:

chkconfig --levels 235 mysqld on
service mysqld start

And get Timeout error occurred trying to start MySQL Daemon.

I checked my logs and see this error:

[ERROR] Fatal error: Can't open and lock privilege tables: Table 'mysql.host' doesn't exist

I'm not sure where to go from here.

For reference I am using RHEL 5 and installed the latest versions of PHP 5 and Apache.

After chown and chgrp'ing /var/lib/mysql per the answer by @Bad Programmer, you may also have to execute the following command:

sudo mysql_install_db --user=mysql --ldata=/var/lib/mysql

Then restart your mysqld.

1. Uninstall mysql using yum remove mysql*

2. Recursively delete /usr/bin/mysql and /var/lib/mysql

3. Delete the file /etc/my.cnf.rmp

4. Use ps -e to check the processes to make sure mysql isn't still running.

5. Reboot server with reboot

6. Run yum install mysql-server. This also seems to install the mysql client as a dependency.

7. Give mysql ownership and group priveleges with:

   chown -R mysql /var/lib/mysql

   chgrp -R mysql /var/lib/mysql

8. Use service mysqld start to start MySQL Daemon.