Para eliminar completamente Mysql de Ubuntu:
sudo apt-get remove --purge mysql-server mysql-client mysql-common
sudo apt-get autoremove
sudo apt-get autoclean
después de esto, si tiene problemas con la reinstalación, intente eliminar los archivos Mysql en:
sudo rm -rf /var/lib/mysql
Espero que esto ayude.
