OK, so we seem to have it working for the majority of people.
I suspect the authoritive DNS servers for the site have their timouts set in such a way that certain ISP DNS server's aren't picking it up properly.
I will take this up with my host further.
Thanks guys!
