I may not have a definite answer but I do have a suggestion. I would temporarily remove the firewall from equation and see what happens. Aalso make sure there are no rules in the router. A PING would typically be disallowed by a firewall.
Try to telnet directly to port 5900 (VNC) on the destination IP address. This will also rule out any application issues. Another question – has this ever worked?