Parece-me um problema de rede, você está por trás de um proxy? Em caso afirmativo, sua configuração pode ser borked.
Dê uma olhada no seu arquivo etc/apt/apt.conf
e verifique as configurações de proxy lá.
( Adicionado pelo usuário em questão após discutir o assunto nos comentários )
SOLUTION miguel@miguel-VirtualBox:~$ cat gedit /etc/apt/apt.conf #Wrong!!! #Acquire::http::Proxy "http://proxyconf/proxy.pac"; Acquire::http::Proxy "http://17X.XX.XX.X:8080";
Foi um problema com as configurações de rede - um proxy inválido estava configurado causando o problema.