A melhor maneira de diagnosticar este problema é procurar em /var/log/mysql/error.log
Isso deve mostrar o motivo pelo qual o MySQL falhou ao iniciar. Se você puder resolver o problema, tente:
dpkg --configure -a
Para concluir a instalação dos seus pacotes.
Se você não pode consertá-lo, você deve ser capaz de remover completamente o mysql com
apt-get purge mysql-server-5.1