Buenas, he creado un nuevo usuario con el host "%" y además le he asignado todos los permisos para trabajar disponibles. Todo esto a través de PhpMyAdmin instaldo en el servidor al que me quiero conectar.
Además de esto he accedido al fichero /etc/mysql/my.cnf y he añadido la linea
bind-adress = 0.0.0.0
y en el fichero /etc/hosts.allow la siguiente
mysqld: all
El problema es que sigue dándome el mismo error.
¿Alguna idea?