Below are the dependencies for 3 versions of apt-utils from apt-cache showpkg.
Perhaps for version 0.9.9.4 the first should be: libapt-instl.5 (2 0.9.9) or at least some version greater than 0.9.7.7, which was the one installed on my system when this problem was happening. Dependencies: 0.9.9.4 - libapt-inst1.5 (2 0.8.0) libapt-pkg4.12 (2 0.9.9.4) libc6 (2 2.4) libdb5.1 (0 (null)) libgcc1 (2 1:4.1.1) libstdc++6 (2 4.4.0) xz-utils (0 (null)) 0.9.7.7 - libapt-inst1.5 (2 0.8.0) libapt-pkg4.12 (2 0.8.16~exp9) libc6 (2 2.4) libdb5.1 (0 (null)) libgcc1 (2 1:4.1.1) libstdc++6 (2 4.4.0) xz-utils (0 (null)) 0.8.15.10 - apt (2 0.8.12) libapt-pkg4.10 (0 (null)) libc6 (2 2.4) libdb5.1 (0 (null)) libgcc1 (2 1:4.1.1) libstdc++6 (2 4.4.0) thanks, --jack