Originally Posted by falko
Do you have valid nameservers in /etc/resolv.conf? Maybe you can try if 18.104.22.168 and 22.214.171.124 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