If it is an ISP problem - I assume that's a problem with the ISPs DNS - would changing the routers DNS to that of say, Google, solve it?

Thanks for the help everyone.