¿Qué tal... hacer lo que está impreso en la terminal?
% sudo apt-get install mysql-client-5.1
o
% sudo apt-get install mysql-client-5.0
(elija la versión correcta según lo que esté instalado en su máquina)
Para instalar CentOS, RedHat y Fedora:
sudo yum install mysql