Esse é um bug conhecido: link
Solução alternativa:
Abra o script de instalação de postagens em /var/lib/dpkg/info/mysql-server-5.6.postinst
e comente a linha 95:
### /usr/share/mysql-common/configure-symlinks install mysql "$mysql_cfgdir/mysql.cnf"
Repetir a instalação.