Il port-forwarding quindi è configurato correttamente? Perchè dovrebbe essere l'unica cosa da fare...
Su che porta ascolta il vnc server?
Prova a pingarlo dal "client" (non è detto che risponda...) e a fare un po' di telnet, prima su una porta che dovrebbe essere aperta, come la 80, e poi su quella del vnc server e vedere cosa dice. Se risponde alla prima porta e non alla seconda allora il port-forwarding non è settato correttamente.