Package: apt Version: 0.9.5.1 Error: Internal Error, No file name for libbz2-1.0 I had a similar issue on my x86_64 box: http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=676635 Packages: http://packages.debian.org/wheezy/amd64/libapt-pkg4.12/download http://packages.debian.org/wheezy/amd64/apt/download To fix I spoke with stew@ and tremon@ in #debian I ran: # Downloaded the appropriate latest apt & libapt packages. dpkg -i apt_0.9.6_amd64.deb libapt-pkg4.12_0.9.6_amd64.deb apt-get update apt-get -f install apt-get update && apt-get dist-upgrade if there are still, issue the following to get more information about your problem: apt-get -o Debug::pkgProblemResolver=yes dist-upgrade |