Che ne dici di... fare ciò che è stato stampato sul terminale?
% sudo apt-get install mysql-client-5.1
o
% sudo apt-get install mysql-client-5.0
(scegli la versione corretta in base a ciò che è installato sulla tua macchina)
Per l'installazione di CentOS, RedHat e Fedora:
sudo yum install mysql