I once had this problem and solved it by installing mysql-server, so make sure that you have installed the mysql-server, not the mysql-client or something else.
That error means the file /var/run/mysqld/mysqld.sock doesn’t exists, if you didn’t install mysql-server, then the file would not exist. So in that case, install it with
sudo apt-get install mysql-server
But if the mysql-server is already installed and is running, then you need to check the config files.
The config files are:
/etc/my.cnf
/etc/mysql/my.cnf
/var/lib/mysql/my.cnf
In /etc/my.cnf, the socket file config may be /tmp/mysql.sock and in /etc/mysql/my.cnf the socket file config may be /var/run/mysqld/mysqld.sock. So, remove or rename /etc/mysql/my.cnf, let mysql use /etc/my.cnf, then the problem may solved.
Try this:
mysql -h 127.0.0.1 -P 3306 -u root -p
Also (to see if it’s running):
telnet 127.0.0.1 3306
Probably it is just a misconfiguration in the my.cnf file, in /etc/somewhere (depending on the Linux distribution).