Conexión remota de mi Ubuntu a MySQL en servidor pagado

[de-troit]

Hola Foreros:

Tengo en mi notebook Ubuntu/Linux con el cliente de MySQL instalado y un servidor pagado para mi página pero sólamente puedo acceder a la BD desde el mismo servidor (desde el panel) pero quiero poder acceder a esa BD remotamente desde la Terminal de mi Ubuntu/Linux (acostumbro a trabajar sin GUI, prefiero la terminal). Fuí al CPanel, creé un usuario, una BD, le di todos los permisos a ese usuario para esa BD, después fuí a la sección "MySQL conexión remota" y añadí mi IP que vi desde una página para ver el IP, como mi IP es dinámica, añadí comodines (xxx.xx.%.%) pero al intentar acceder por la Terminal de mi notebook de la forma:

mysql -h HOST -u USER -p
(y luego pongo la clave cuando me la solicita)

...no me lo permite y retorna el siguiente aviso:

ERROR 2003 (HY000): Can't connect to MySQL server on 'xx.xx.xxx.xxx' (110)

Qué podrá ser? Alguien logró solucionar este problema?

Espero que me puedan ayudar, cualquier tipo de ayuda o datos sirven.

Soy principiante en esto, así que traten de redactar para un principiante, para así poder entender sin problemas, disculpen las molestias.

Muchas gracias :)