I know this is late advice, but I got that a lot. One thing you can try is to manually add some new DNS servers to your connection. Assuming you use GNOME, just right click the network connection icon in your tray and click on "Edit connections" (or whatever it says). Then go to the Wired or Wireless tab and click on your connection. It'll say something like "Auto Wireless - 3 minutes ago". Then click on Edit to the right. Give your password if you need to.
Now in the "Editing (connection name)" window, go to the "IPv4 Settings" tab. Change Method to "Automatic (DHCP) addresses only". Now you can alter the DNS servers line below. I use one OpenDNS server ans one Google DNS server.
Note the comma and space between the servers' IP addresses. Then click Save... (If you can't recheck your IP addresses entered. When it's in the proper syntax, you can save.) and your connection will restart. With any luck, that should fix the problem.
It seems to me that some ISPs have poor, or even broken, DNS routing when it comes to Linux package repos.