Em suma, o Ubuntu 16.04 fornece apenas pacotes para o MySQL 5.7. O que significa que manter a versão 5.6 não permitirá que você atualize.
O bloqueio que você está fazendo está exatamente como deveria; que está impedindo que ele atualize o MySQL para a versão 5.7. No entanto, ele também está atrasando sua atualização para o Ubuntu 16.04.
Durante a pesquisa, encontrei um link para algumas informações sobre como adicionar o MySQL 5.6 ao Ubuntu 16.04: link
Talvez você possa despejar seu banco de dados, remover o MySQL, atualizar para o 16.04, instalar o MySQL 5.6 usando as informações vinculadas acima e depois restaurar o banco de dados? Certifique-se de ter um backup apenas no caso de não funcionar.