Conexión remota a base de datos MySQL

Estoy intentando conectarme con un servidor de MySQL que está en otra máquina remota. Los dos servidores desde donde estoy trabajando son servidores de Internet que están en el mismo proveedor. En uno tengo la base de datos únicamente, y en otro servidor tengo los archivos de la aplicación. Así que desde un servidor me tengo que conectar a la base de datos que está en otro servidor remoto.

Intento de todos los modos conectarme, pero no lo consigo. MySQL me responde con un código de error como este:

ERROR 2003 (HY000): Can't connect to MySQL server on '0.1.1.1' (111 "Connection refused")

No debe de ser el firewall, porque si no entiendo que MySQL no te daría ninguna respuesta.

He hecho todo el proceso para realizar una conexión remota con MySQL / MariaDB.

He creado un usuario, indicando la IP desde donde voy a conectar:

create user user@0.1.2.3;

(He editado la IP para publicar, obviamente no es la 0.1.2.3)

He aplicado los permisos correspondientes con la sentencia siguiente:

grant all on nombre_de_mi_base_de_datos.* to user@0.1.2.3 IDENTIFIED BY '1234qwer';

Luego he corrido el comando de procesar los privilegios:

flush privileges;

Por si fuera poco he reiniciado MySQL:

sudo service mysql restart

Y como no me funcionaba también hice un reboot del servidor. Comando "reboot".

Por si sirve de ayuda, estoy trabajando con un servidor Ubuntu Server, tanto en el servidor de la base de datos como de la aplicación. En el servidor de la base de datos he corrido el comando "mysql_secure_installation" para dejar la instalación más segura.

El intento de conexión lo estoy haciendo desde el cliente de MySQL, de esta manera:

mysql -h 0.1.2.3 -u user -p

Alguien tiene alguna sugerencia sobre alguna otra cosa que pueda realizar para conectar con MySQL en un servidor remoto? Gracias!