Parece que muitos aplicativos dependem do /var/run/utmp para informações da sessão de logon.
sudo touch /var/run/utmp
sudo chmod 664 /var/run/utmp
sudo reboot
após a reinicialização, execute estes comandos, como sugerido pela @coteyr, para limpar o mysql
sudo apt-get purge mysql-server
sudo apt-get update
sudo apt-get install mysql-server
Isso deve resolver seu problema.
EDITAR:
sudo apt-get purge mysql-server
sudo apt-get purge mysql-common
sudo rm -rf /var/log/mysql
sudo rm -rf /var/log/mysql.*
sudo rm -rf /var/lib/mysql
sudo rm -rf /etc/mysql
sudo apt-get install mysql-server --fix-missing --fix-broken
Isso parece estar funcionando para muitas pessoas, de acordo com essa postagem no blog