É possível que a fonte da qual o arquivo deve ser baixado esteja desativada.
Se isso acontecer com todo o software no Ubuntu Software Center, possivelmente as Fontes de Software foram modificadas? (Configurações do Sistema / Fontes de Software) Verifique se as fontes desejadas estão marcadas.
TAMBÉM: Eu me lembro de brincar com proxy e não percebi que tinha adicionado um para as configurações ... XD