Você tem um proxy na sua empresa? Se assim for, você pode definir o proxy antes de executar a atualização do apt-get logado como root primeiro:
export http_proxy=http://host:port
apt-get update
Usando o sudo:
sudo http_proxy=http://host:port apt-get update
Se o seu proxy exigir autenticação, você pode configurá-lo na URL ( cuidado com o fato de a senha ser salva no histórico como texto simples ):
http://username:password@host:port