For future reference...
...once you have checked for firewalls etc stopping access when you are trying this its worth checking with the ISP at both ends.
I found out I could not use VNC to remote admin my parent's PC because Virgin block access to the ports VNC use as they consider VNC to be a business use. Funnily enough they do not advertise their service as a restricted internet package.