无法从PHP连接到MySQL,但可以从CLI连接

Since today morning I cannot connect to my MySQL from any of the two web servers via PHP, but I can connect via command line

I've checked, there is no bind-address in the /etc/my.conf, the user with which I'm connecting has all privileges and is allow to connect as

'<user>'@'%'
'<user>'@'localhost'
'<user>'@'127.0.0.1'
'<user>'@'<web-server-1-ip-internal>'
'<user>'@'<web-server-1-ip-external>'
'<user>'@'<web-server-2-ip-internal>'
'<user>'@'<web-server-2-ip-external>'

(above external is fully resolved ip and internal is 10.xxx.xxx.xxx)

I've tried to start/restart and reinstall the mysql server, there's nothing in the error logs (/var/log/mysqld.log is actually a few days old which is weird).

I'm using a simply php script to connect

<?php

$link = mysql_connect('<db-server-ip>', '<user>', '<password>');
if (!$link) {
    die('Could not connect: ' . mysql_error());
}
echo 'Connected successfully';
mysql_close($link);

?>

This gives me the

Could not connect: Lost connection to MySQL server at 'reading initial 
communication   packet', system error: 110

I did check firewall rules and /etc/hosts.allow and /etc/hosts.deny as well as (although this can't be the issue as CLI connection works just fine)

Any ideas short of rebuilding the server (which may not help anyways)