Mi sembra un problema di permessi, sta facendo lo start da root?
Prova questi:

# cd /var/lib
# chown -R mysql mysql mysql
# chgrp -R root mysql mysql
# su mysql
# mysql_install_db --user=mysql
# mysqld_safe --user=mysql