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