Eu acho que você não tem o MySQL rodando. Tente iniciá-lo usando
$ sudo service mysql start
Se você ainda receber erros, verifique no syslog se há alguma informação
$ grep mysql /var/log/syslog
Se você não consegue descobrir o problema, você também pode atualizar sua resposta com o log usando pastebinit
$ grep mysql /var/log/syslog | pastebinit
Além disso, verifique se o diretório /var/run/mysqld/
existe e concorda com o usuário mysql.
$ ls -la /var/run/mysqld
total 4
drwxr-xr-x 2 mysql root 80 Nov 5 21:24 .
Se nada resolver o problema, talvez a melhor maneira seja remover completamente o MySQL e instalá-lo novamente.
AVISO: isso excluirá todos os seus dados do MySQL. Portanto, se você tiver dados importantes em bancos de dados MySQL, faça um backup primeiro!
sudo apt-get purge mysql-server mysql-common
sudo rm -rf /var/lib/mysql
sudo apt-get clean
sudo apt-get install mysql-server
Editar
Eu encontrei este bug que parece semelhante ao seu. Há uma solução lá por Simon Hill que pode funcionar com você : criando um arquivo /etc/apparmor.d/tunables/proc
(se ainda não existir) com o seguinte conteúdo:
# ------------------------------------------------------------------
#
# Copyright (C) 2006 Novell/SUSE
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of version 2 of the GNU General Public
# License published by the Free Software Foundation.
#
# ------------------------------------------------------------------
# @{PROC} is the location where procfs is mounted.
@{PROC}=/proc/