Как полностью удалить пакет в Ubuntu?
sudo apt-get purge mysql-server-5.6
apt-get clean
если не помогло, открываем файл /var/lib/dpkg/status
удаляем строки касающиеся mysql-server-5.6, и устанавливаем его заново если нужно.
попробуйsudo dpkg --remove --force-remove-reinstreq mysql-server