Here's my attempt at getting this one fixed. Unfortunately I can't claim to have any deep understanding of dpkg's workings after what perusing I did, but it still seems to fix this. At least it fixed the test case shown.
This'll still need at least some refactoring. The error message handling is pretty much identical with the code prior to my code, those could be merged and moved to their own function. Also, the error message generated is a bit off. If nothing else, then the apparent simplicity of the patch bothers me... I hope it's of any use.
diff -urp dpkg-1.13.10/src/packages.c dpkg-1.13.10.new/src/packages.c --- dpkg-1.13.10/src/packages.c 2005-06-06 07:07:12.000000000 +0300 +++ dpkg-1.13.10.new/src/packages.c 2005-07-21 01:00:33.644014266 +0300 @@ -408,6 +408,45 @@ int dependencies_ok(struct pkginfo *pkg, internerr("unknown value for found"); } } + + if (!removing && pkg->installed.depended) { + for (possi= pkg->installed.depended; possi; possi = possi->next) { + if (possi->up->type != dep_depends && possi->up->type != dep_predepends) + continue; + matched= 0; varbufreset(&oemsgs); + thisf= deppossi_ok_found(possi->ed, possi->up->up, 0, 0, &matched, possi, + &interestingwarnings, &oemsgs); + + switch (thisf) { + case 0: + ok= 0; + case 2: + varbufaddstr(aemsgs, " "); + varbufaddstr(aemsgs, possi->up->up->name); + varbufaddstr(aemsgs, _(" depends on ")); + varbufdependency(aemsgs, possi->up); + if (interestingwarnings) { + /* Don't print the line about the package to be removed if + * that's the only line. + */ + varbufaddstr(aemsgs, _("; however:\n")); + varbufaddc(&oemsgs, 0); + varbufaddstr(aemsgs, oemsgs.buf); + } else { + varbufaddstr(aemsgs, ".\n"); + } + break; + case 1: + if (ok>1) ok= 1; + break; + case 3: + break; + default: + internerr("unknown value for found"); + } + } + } + if (ok == 0 && (pkg->clientdata && pkg->clientdata->istobe == itb_remove)) ok= 1;