Recientemente, para probar, contraté un Virtual Private Server (VPS) con OpenVZ. Tuve problemas para instalar mysql-server porque daba error con InnoDB.
Estuve buscando y encontré la solución: añadir en el fichero /etc/mysql/my.cnf la siguiente línea:
skip-innodb
Como nota final, he de decir que un VPS sobre XEN va infinitamente mejor que uno con OpenVZ. Con OpenVZ se suelen «sobrevender» los recursos mientras que con XEN se reservan para ti los que contratas.