> gzipを削除しようとしてもできない
ってどういう意味？
rm /bin/gzip をしてできないって意味？
だとしたら二重の意味で間違ってる。

多分 Packages.gz のファイルが壊れてるので、
/var/lib/apt/lists/ 以下の該当ファイルを削除してもう一度
apt-get update すれば直るかもしれない。