Originally Posted by falko
Do you have valid nameservers in /etc/resolv.conf? Maybe you can try if 184.108.40.206 and 220.127.116.11 work (Google's nameservers).
Yes, I do have valid name servers as it works fine with no firewall.
However, I do believe I have this sorted now as I logged a support ticket to get my ISP to move my VSP to a different host, and now it works absolutely fine. Very weird - perhaps they have a misconfigured host, but it's all good now.
Thanks for your help