Can't connect to mysql server (Error 2003, (110))

Bonjour.
Quand j'essaye de me connecter en sql à partir d'une Machine Virtuelle VM1 du site OVH sur une autre VM VM2 du site OVH, j'ai l'erreur suivante (xxxx cache le mot de passe):

(17:40:25) root@vm1-ovh:~# mysql -h adresse_IP_VM2 -u replication_user -pxxxxxxx -P 3306
ERROR 2003 (HY000): Can't connect to MySQL server on 'adresse_IP_VM2' (110)

La connexion mysql interne dans la VM_2 est OK

(17:40:35) root@vm2-ovh:~# mysql -u replication_user -pxxxxx -P 3306
Welcome to the MySQL monitor. Commands end with ; or \g.
Your MySQL connection id is 18242
Server version: 5.1.73-1-log (Debian)

Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved.

Oracle is a registered trademark of Oracle Corporation and/or its
affiliates. Other names may be trademarks of their respective
owners.

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql>

NB: la connexion à cette VM à partir d'une machine qui se situe sur mon réseau local (pas sur OVH) est OK.

(17:42:35) root@vm3-locale:~# mysql -h adresse_IP_VM2 -u replication_user -pxxxxx -P 3306
Welcome to the MySQL monitor. Commands end with ; or \g.
Your MySQL connection id is 18247
Server version: 5.1.73-1-log (Debian)

Type 'help;' or '\h' for help. Type '\c' to clear the buffer.

mysql>

Il est à préciser qu'il n'y a pas de firewall qui bloque au niveau de cette VM2 et que SELinux is désactivé (0 dans le fichier /selinux/enforce).

Extrait du fichier /etc/mysql/my.cnf

[client] 
port = 3306 
socket = /var/run/mysqld/mysqld.sock 

[mysqld_safe] 
socket = /var/run/mysqld/mysqld.sock 
nice = 0 

[mysqld] 
user = mysql 
pid-file = /var/run/mysqld/mysqld.pid 
socket = /var/run/mysqld/mysqld.sock 
port = 3306 
basedir = /usr 
datadir = /var/lib/mysql 
tmpdir = /tmp 
language = /usr/share/mysql/english 
skip-external-locking 


log-bin=/var/log/mysql/mysql-bin.log 
binlog_do_db = teamberdev 
server-id=1 

#bind-address = 91.121.239.234 
#bind-address = 0.0.0.0 

key_buffer = 16M 
max_allowed_packet = 16M 
thread_stack = 192K 
thread_cache_size = 8 

myisam-recover = BACKUP 
query_cache_limit = 1M 
query_cache_size = 16M 

log_slow_queries = /var/log/mysql/mysql-slow.log 
long_query_time = 2 
log_error = /var/log/mysql/mysql-errors.log 

expire_logs_days = 10 
max_binlog_size = 100M 

[mysqldump] 
quick 
quote-names 
max_allowed_packet = 16M 

[mysql] 
#no-auto-rehash # faster start of mysql but no tab completition 

[isamchk] 
key_buffer = 16M 

!includedir /etc/mysql/conf.d/

Toutes les autres options sont commentées

Avez vous une idée pour résoudre ce problème.
Si nécessaire, je vous enverrai des extraits des fichiers de config.