O problema é o jeito que você está tentando instalar o mysql, quando você faz apt-get install mysql*
ele tenta instalar 50 ou mais pacotes e programas diferentes, alguns dos quais não podem ser instalados juntos e outros que não podem ser instalados sem outros dependências. Geralmente são programas especializados.
Para instalar, basta executar:
sudo apt-get install mysql-server