Assumindo que você tentou instalar o mysql-client-core-5.6 primeiro.
Abra o seu terminal e digite:
sudo apt-get purge mysql-client-core-5.6
sudo apt-get autoremove
sudo apt-get autoclean
sudo apt-get install mysql-client-core-5.5
sudo apt-get install mysql-server