Eu tenho o mesmo problema. O Software Updater mal tenta e depois desiste de verificar a minha conexão com a Internet.
Funciona bem quando eu faço isso do terminal, como o lukibeni sugeriu.
sudo apt-get update
sudo apt-get upgrade
Atualizando do terminal eu obtenho 100kB / s consistentes, o que não é velocidade de banda larga, mas funciona claramente, Software Updater. Pelo menos para alguns subconjuntos de usuários, a ferramenta atualizadora de software está praticamente quebrada.
Eu vejo outra resposta ( link ) sobre como acessar as opções de fontes de software e alterar o servidor do qual você recebe atualizações. Isso não funcionou para mim.