Eu decidi remover todos os pacotes que apt estava me sugerindo, incluindo (muon-updater, qt-propeties e outros, como você pode ver na captura de tela). Eu estava com medo de fazer isso, porque são pacotes muito importantes, mas tudo funciona muito bem;) Mas nem todo comando purge / remove sugere que você apague uma grande quantidade de pacotes.
Eu usei este aqui:
sudo apt-get remove --purge mysql-server mysql-client mysql-common
Após os pacotes de desinstalação, consegui instalar mysql-server
sem nenhum erro.