Eu enquanto consertava um problema tive que remover o Ubuntu Software Center (parecia buggy). Também minha rede funciona em proxy e requer autenticação de nome de usuário e senha que me permite baixar e instalar arquivos através do terminal.
Eu postei o problema aqui você pode dar uma olhada (em relação à autenticação de proxy).
Então, por favor, forneça uma solução para instalar o Ubuntu Software Center novamente e configure as configurações de proxy para o terminal também.
P.S. A Internet funciona bem no Firefox.