Tente isso -
sudo apt-get remove --purge mysql-server mysql-client mysql-common
sudo apt-get autoremove
sudo apt-get autoclean
Em seguida, reinstale:
sudo apt-get update
sudo apt-get install mysql-server mysql-client
Pode ser o autoclean e a atualização que fazem a diferença.