Eu também estou usando o Ubuntu 16.10, e a versão padrão do servidor mysql no meu computador é 5.7 e está funcionando bem.
Tente os seguintes comandos:
sudo apt-get install -f
sudo apt-get purge mysql-server-5.6
sudo apt-get update && sudo apt-get install mysql-server-5.7
Se você ainda receber um erro de pacotes quebrados, tente sudo dpkg --configure -a
para corrigi-lo. Este também pode ser útil para você corrija pacotes quebrados.
(PS: Isso pode não funcionar, eu coloquei minha resposta porque eu não tenho reputação suficiente para comentar, espero que possa ajudá-lo!)