A resposta está nos comentários, mas acho que vale a pena postar lá.
Eu baixei o mysql-apt-config_0.7.2-1_all.deb (repositório do MySQL APT - dev.mysql.com/downloads/repo/apt) em dev.mysql.com e durante a configuração eu escolhi o Ubuntu Wily desde 16.04 não na lista. E esse era o problema, o Xenial já tem o MySQL 5.7 em seus repositórios oficiais.
Corrigi-o executando sudo apt-get purge mysql-apt-config
e, em seguida, sudo apt install mysql-server
.
Eu quero dizer que você deve agradecer fkraiem , não eu.