SOLUÇÃO NA SEÇÃO EDITAR
Eu sei o motivo, ainda estou tentando encontrar uma solução para isso.
Só para ter certeza de que sua situação é como a minha, corra:
dpkg -l | grep mysql
você deve ver a maioria dos pacotes na versão 5.6.x, exceto um par, especialmente o mysql-common, que é 5.7.x.
Conforme especificado na descrição do pacote:
% bl0ck_qu0te%Basicamente, qualquer mysql-x-5.6 depende do mysql-common, que neste caso vem do repositório principal, então é para o 5.7, e se você tentar instalar manualmente o mysql-common-5.6, ele entrará em conflito ou dependerá mysql-common (porque nas versões anteriores do Ubuntu era 5.6).
Ainda não encontrei uma solução para isso, mas talvez com essa informação adicional alguém possa criar uma.
EDIT: Encontrei uma solução, parece ser a mais fácil. Primeiro, remova todos os pacotes e arquivos do mysql (faça backup dos mais importantes):
apt purge mysql*
apt autoremove
apt autoclean
rm -rf /etc/mysql/
Agora você deve estar limpo.
Agora, vá aqui e baixe a versão que você precisa, ele contém todas as dependências, exceto libaio1 então:
apt install libaio1
tar -xvf downloadedMysqlPackage.tar
dpkg -i mysql-common-xxx.deb
dpkg-preconfigure mysql-community-server-xxx.deb
dpkg -i mysql-community-server-xxx.deb
dpkg -i mysql-community-client-xxx.deb
dpkg -i libmysqlclient18-xxx.deb
E você é bom para ir!