Perhaps you need to create that directory first:

mkdir /var/lib/mysql
chown mysql:mysql /var/lib/mysql
/etc/init.d/mysql start

Something else you could try. The mysql update script is run out of /etc/init.d/mysql here:

# Run mysql_upgrade on every package install/upgrade. Not allways
# necessary, but doesn't do any harm.
if test -f $datadir/.run-mysql_upgrade ; then

Since this is a new install, it shouldn't have to, so remove /var/lib/mysql/.run-mysql_update before starting mysql.