O principal problema é que a instalação mínima do Ubuntu não tem tudo o que você precisa.
O post Pacote mysql-server-5.5 ainda não está configurado fornece a solução para o seu problema. Eu sugiro que você leia isso. No entanto, vou fornecer um breve resumo abaixo.
Limpe a antiga instalação do mysql.
sudo apt-get purge mysql*
sudo apt-get autoremove
sudo apt-get autoclean
Atualize as coisas que estão faltando na instalação mínima do Ubuntu.
sudo apt-get dist-upgrade
Instale o MySql como normal:
sudo apt-get install mysql-server
Se isso ainda não funcionar, você pode fazer
sudo apt-get install mysql-server --fix-missing --fix-broken