Primeiro de tudo, tente
sudo apt-get clean
sudo apt-get update && sudo apt-get upgrade
Alguns ISPs armazenam em cache os pacotes e erros como esses são relatados. Se os comandos acima não funcionarem, tente
sudo apt-get update -o Acquire::http::No-Cache=True
e novamente
sudo apt-get update && sudo apt-get upgrade
Se ainda não funcionar,
sudo apt-get update -o Acquire::BrokenProxy=true
sudo apt-get update && sudo apt-get upgrade
Se tudo estiver definido, você pode torná-lo permanente, para que nenhum problema no futuro persista, editando
/etc/apt/apt.conf
APT
{
// Options for the downloading routines
Acquire
{
http
{
No-Cache "true";
};
};
}