VNC connection from USA to Korea

Hello,
We have a customer in Korea that has previously allowed us VNC connections from our site.  It recently stopped working.  They swear that the ports are open on their side, and they can VNC from home to this office site.
We are able to VNC to other remote sites just find.
For this host, they do have ping turned off.

What other things can we do to trouble shoot this.
A traceroute to their site end like this (I omitted our & their IP addresses for now):

5  bb1-p8-0.crsfca.sbcglobal.net (151.164.243.2)  5.256 ms  5.136 ms  5.348 ms
 6  ex1-p3-0.eqsjca.sbcglobal.net (151.164.41.101)  6.406 ms  6.963 ms  6.943 ms
 7  ex2-p10-0.eqsjca.sbcglobal.net (151.164.191.67)  7.088 ms  7.160 ms  7.188 ms
 8  as174.eqsjca.sbcglobal.net (151.164.248.250)  7.273 ms  6.708 ms  6.546 ms
 9  g11-0-0.core01.sjc01.atlas.cogentco.com (154.54.1.29)  6.953 ms  7.053 ms  6.819 ms
10  p13-0.core01.lax01.atlas.cogentco.com (66.28.4.73)  20.033 ms  20.421 ms  20.560 ms
11  p15-0.core01.lax04.atlas.cogentco.com (154.54.1.54)  20.242 ms  20.357 ms  20.307 ms
12  kddi.demarc.cogentco.com (38.112.7.98)  177.250 ms  179.006 ms  177.251 ms
13  202.30.243.81 (202.30.243.81)  161.361 ms  161.961 ms  162.084 ms
14  202.30.243.34 (202.30.243.34)  160.945 ms  163.932 ms  161.133 ms
15  * * *
16  202.30.148.6 (202.30.148.6)  236.954 ms  247.492 ms  302.503 ms
17  * * *
18  * * *
19  * * *
20  * * *
21  * * *
22  * * *