De alguma forma, seu sistema de pacotes foi danificado. Aparentemente, o arquivo /etc/init.d/mysql
foi perdido no progresso. Adicione um manequim para auxiliar o sistema de pacotes sobre a perda:
$ sudo -i
# cat > /etc/init.d/mysql << EOF
> #!/bin/true
> EOF
# chmod 755 /etc/init.d/mysql
... e depois remova todos os pacotes do mysql ...
# apt-get remove --purge mysql-server-5.5 mysql-server
Isso também deve remover o script fictício. Se não, exclua manualmente. Depois disso, você poderá instalar o mysql como normal novamente.