Communications link failure while connecting to local databases

When trying to connect to my local MySQL server via JDBC, I get the following error:

com.mysql.jdbc.exceptions.jdbc4.CommunicationsException: Communications link failure

The last packet sent successfully to the server was 0 milliseconds ago. The driver has not received any packets from the server.

I tried to figure it out browsing the internet, but I can't find a solution that works for me. This is what I tried:

1) Exchanging localhost and 127.0.0.1 in the connection URL in the java program.
2) Trying to connect to a different database (derby) which fails with a network error.
3) Checked whether the port was open in iptables (it is).
4) Checked the bind address in my.cnf and changed it to localhost/127.0.0.1 respectively without success.
5) Added localhost and 127.0.0.1 to ignored hosts in the network proxy settings.
6) Re-installed mysql server.
7) Verified that --skip-networking is not in my.cnf.
8) Tried different JDBC drivers (.14-.16).

I'm using MySQL server 5.1.54-1ubuntu4 and java-6-sun-1.6.0.24 with the current JDBC driver. Also, I noticed this behavior:

mysqladmin -h 127.0.0.1 version

mysqladmin: connect to server at '127.0.0.1' failed error: 'Lost connection to MySQL server at 'reading initial communication packet', system error: 0'

mysqladmin -h localhost version

mysqladmin Ver 8.42 Distrib 5.1.54, for debian-linux-gnu on x86_64...

I'd appreciate any help!