You need to remove the /var/lib/mysql folder. Also, purge when you remove the packages (I'm told this helps).
sudo apt-get remove --purge mysql-server mysql-client mysql-common
sudo rm -rf /var/lib/mysql
I was encountering similar issues. The second line got rid of my issues and allowed me to set up MySql from scratch. Hopefully it helps you too!