tldr; Software Source -> Download From -> Other -> Choose Best Server
I had this problem with an ubuntu install. To debug the problem I edited
/etc/apt/apt.conf and added
which gives a really short timeout and makes it much more obvious what the problem is.
apt-get update then showed a lot of 404's from
http://bg.archive.ubuntu.com which was the repository my ubuntu install had chosen.
Under software sources I then went to Download From -> Other -> Choose Best Server. It chose a server in Bulgaria - which actually happened to be the same server, which I suppose bg.archive.ubuntu.com is aliased or redirected to. But in any case, after selecting that server directly rather than the .archive.ubuntu.com alias, apt-get update worked perfectly. This suggests there can sometimes be some kind of problem with DNS or aliasing with the *.archive.ubuntu.com server names, which can simply be resolved by using another server, or even the same server directly by it's non-aliased name.