Parece que você tem um erro no seu perfil apparmor para o mysql. Ao consertá-lo, você pode desabilitar o perfil do apparmor para o mysql e o mysql deve funcionar:
sudo ln -s /etc/apparmor.d/usr.sbin.mysqld /etc/apparmor.d/disable/usr.sbin.mysqld
e reinicie o apparmor com: sudo /etc/init.d/apparmor restart
Quando você tem o perfil do mysql apparmor corrigido, você pode remover o symlink e reiniciar o apparmor.
UPDATE2:
Novos passos para remover e reinstalar o mysql:
sudo apt-get purge mysql-server mysql-client mysql-common mysql-client-5.5 mysql-server-5.5
sudo apt-get autoremove
sudo apt-get autoclean
sudo rm -rf /etc/mysql
sudo apt-get install mysql-server mysql-common mysql-client
(deve pedir uma nova senha de administrador)
Verifique se funciona:
sudo service mysql status
Se isso não funcionar, verifique se você tem um arquivo /etc/mysql/my.cnf
. Se não, copie-o do padrão e reinicie o mysql:
sudo cp /etc/mysql/my.cnf.dpkg-dist /etc/mysql/my.cnf