I just encountered this bug on lenny. For anyone who doesn't know, the temporary work around for this is to update like this as root (or using sudo): aptitude update -o Acquire::PDiffs=false or apt-get update -o Acquire::PDiffs=false