We also use Vodafone broadband, a fix i found is:
Go into your routers config page (192.168.1.1).
Enter your admin password into the box that comes up.
Click on the internet tab.
Along the left should be 4 choices under the internet tab, click the DNS / DDNS option.
Now change the DNS...