Eu tive o mesmo problema há algumas horas. Primeiro eu matei o processo travado (kill -9 PID, ou complete o restart) então eu completamente desinstalei o mysql.
sudo apt-get remove --purge mysql-server mysql-client mysql-common
ou
sudo apt-get remove --purge mysql*
Isto irá desinstalar todos os pacotes relacionados ao mysql, o que na maioria dos casos é um pouco exagerado ...
Tenha o cuidado de fazer uma cópia de seus bancos de dados antes de fazer isso ou simplesmente não exclua o banco de dados quando o processo de desinstalação perguntar sobre ele. Então reinicie novamente (ou mate o processo do mysql-apt-config) e remova o pacote mysql-apt-config.
sudo apt-get remove --purge mysql-apt-config
sudo apt-get autoremove
Após esses passos eu instalei novamente tudo resolveu o problema.
sudo apt-get install mysql-server libapache2-mod-auth-mysql php5-mysql
Não tenho certeza, mas provavelmente é o suficiente para reinstalar apenas o mysql-apt-config. Boa sorte pessoal!