Bem, só posso recomendar que você tente
"sudo apt-cache search mysql"
para encontrar tudo relacionado.
"sudo apt-get purge mysql *"
para remover tudo relacionado.
Além disso, é recomendado usar o aptitude em vez do apt, mas se você começou com apt, mantenha-o.