Eu sei que isso é um pouco antigo, mas recebi o mesmo erro com o apt-get no Ubuntu GNOME 16.04.1 LTS. Eu encontrei uma antiga postagem no fórum que pareceu resolver os problemas apt para mim. Aqui estão os passos recomendados:
sudo -i
apt-get clean
cd /var/lib/apt
mv lists lists.old
mkdir -p lists/partial
apt-get clean
apt-get update
cd
exit