Сбрасывать ещё и VersionedKernelPackages:
% cat cleanup-kernels #clear APT::NeverAutoRemove; #clear APT::VersionedKernelPackages;
-- sergio.