Данный метод удалит все, что связано с MySQL. Повторная установка MySQL будет как на чистой системе. Не забываем сначала скопировать каталог с базой MySQL если она Вам нужна и другие необходимые базы данных из каталога /var/lib/mysql/ и только затем приступать к удалению MySQL.
Удалить MySQL с помощью aptitude:

sudo aptitude purge mysql-client mysql-server mysql-common
sudo atitude autoclean

Найти все файлы включающие буквы «mysql» и удалить:

sudo find / -iname ‘mysql*’ -exec rm -rf {} \;

Установка MySQL

sudo aptitude update
sudo aptitude install mysql-client mysql-server mysql-common

Если доступно несколько версий MySQL, последнею можно узнать:

sudo aptitude search mysql-client mysql-server mysql-common

На данный момент доступна версия 5.5 (по умолчанию) и 5.6.

Для установки последней доступной версии MySQL из apt необходимо явно указать версию:

sudo aptitude install mysql-client-5.6 mysql-server-5.6 mysql-common-5.6

Теперь немножко позаботимся о нашей безопасности, вводим в консоль:

mysql_secure_installation

На все вопросы кроме «Change the root password» (Если не хотите менять пароль MySQL) отвечаем положительно Y.