$ sudo service mysql start
mysql start/running

$ mysql -u root
ERROR 2002 (HY000): Can't connect to local MySQL server through socket '/var/run/mysqld/mysqld.sock' (2)

$ aptitude search mysql |grep ^i
i   libapache2-mod-auth-mysql       - Module Apache 2 pour l'authentification vi
i   libdbd-mysql-perl               - Perl5 database interface to the MySQL data
i   libmysqlclient16                - MySQL database client library
i   mysql-client-5.1                - MySQL database client binaries
i   mysql-client-core-5.1           - MySQL database core client binaries
i   mysql-common                    - MySQL database common files, e.g. /etc/mys
i   mysql-server-5.1                - MySQL database server binaries and system
i   mysql-server-core-5.1           - MySQL database server binaries
i   php5-mysql                      - MySQL module for php5

sudo apt-get install mysql-server-5.1 --reinstall

sudo dpkg-reconfigure mysql-server-5.1

Mysql-u root-p
Enter password:
ERROR 2002 (HY000): Can not connect to local MySQL server-through socket '/ tmp / mysql.sock' (2)

# ps -fea | grep mysqld
mysql    17661 14003  1 Feb19 ?        00:24:59 /usr/local/mysql-percona/libexec/mysqld --basedir=/usr/local/mysql-percona --datadir=/var/data/mysql/datadir/data --user=mysql --pid-file=/var/run/mysqld/mysqld.pid --skip-external-locking --socket=/var/lib/mysql/mysql.sock --log-error=/var/log/mysqld.log
root     23790  7840  0 09:25 pts/0    00:00:00 grep mysqld

grep socket /etc/my.cnf
socket=/var/lib/mysql/mysql.sock

[client]
default-character-set=utf8
socket=/var/lib/mysql/mysql.sock

I came to the similar error when I failed to upgrade mysql-server package， but I found this solved my problem.
When `sudo apt-get install -f` doesn't work, try `sudo apt-get purge mysql*`. Now you can reinstall mysql-server.