Administración remota de equipos...

Esto pudiera tener una causa probable; es posible que en tu red tengas un firewall instalado que tenga blequeado el puerto 5900 que es el puerto Default del VNC (verifica el tuyo), o el proxy que utilizas para compartir internet no habilite el puerto en cuestión en la conexión a internet. Para cualquiera de las premisas lo más probable que el problema sea de puertos.
Te recuerdo lo obvio: utiliza la IP de la maquina para conectarte, no utilices el nombre del PC ya que en internet se trabaja con nombre de dominios.
Suerte y saludos.

Estimado experto:
¿Hay alguna de forma de saber si el puerto que me indicas esta bloqueado?
Efectivamente si estoy utilizando la IP de la PC a la que me quiero conectar.
Gracias.

Ubícate el programa Superscan (escáner de puertos) y aplícalo en la pc a la que te quieras conectar. Te dirá que puertos tiene abierto esa maquina. Si está cerrado debes configurar bien sea el Firewall que tienes en la red o el proxy que utilizas para distribuir internet en toda la red.
Suerte.