Eu tentei usar o aptitude para resolver os conflitos e ele me deu informações adicionais, mas eu tive que remover os vários pacotes mysql e depois reinstalá-los:
apt-get purge mysql-server*
apt-get install mysql-server
Eu não consegui corrigir o problema sem primeiro desativar o banco de dados momentaneamente ...