Turns out Upstart start up jobs can have problems on OpenVZ.
Changing:
start on (net-device-up and local-filesystems and runlevel [2345]) to:
start on runlevel [2345] fixed the problem for me.
Original source http://askubuntu.com/questions/15222/mysql-server-upstart-script-not-working-on-boot