Qual versão você usa? Você está usando proxy?
EDITAR:
Para usar o apt-get através de um proxy, eu faço o seguinte -
sudo apt-get --print-uris install PROGRAM
Isto imprime os URLs dos pacotes, para que você possa baixá-los. Por exemplo, usando supertux:
wilf@comp:~$ sudo apt-get install --print-uris supertux
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following extra packages will be installed:
supertux-data
The following NEW packages will be installed
supertux supertux-data
0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
Need to get 59.4 MB of archives.
After this operation, 80.0 MB of additional disk space will be used.
Do you want to continue [Y/n]?
Em seguida, faça o download dos arquivos .deb dos links fornecidos, por meio de um navegador que funcione por meio do proxy, e você poderá instalá-los usando o Software Center ou usando o terminal com este comando cd /FOLDER/WITH/DOWNLOADED-DEB-FILES; dpkg -i *.deb ER cd .... ; gdebi *.deb . Lenta e chata, mas parece funcionar.
EDIT2: (Método Fácil) (do site help.ubuntu.com)
Método do arquivo de configuração do APT
Este método usa o arquivo apt.conf que é encontrado em seu diretório / etc / apt /. Este método é útil se você quiser que o apt-get (e não outros aplicativos) use permanentemente um http-proxy.
Em algumas instalações, não haverá configuração do arquivo apt-conf. Este procedimento irá editar um arquivo apt-conf existente ou criar um novo arquivo apt-conf.
gksudo gedit /etc/apt/apt.conf
Adicione esta linha ao seu arquivo /etc/apt/apt.conf (substitua seus detalhes pelo seu endereço de proxy e proxyport).
Acquire::http::Proxy "http://yourproxyaddress:proxyport";
Salve o arquivo apt.conf.
Se o seu proxy precisar de um login / senha, substitua:
"http://yourproxyaddress:proxyport";
com
"http://username:password@yourproxyaddress:proxyport";
Algo como seguir deve funcionar bem
Acquire::http::proxy "http://lgn:[email protected]:8080/";
Acquire::https::proxy "http://lgn:[email protected]:8080/"