Debian’s apt-get won’t succeed here, because AFAIK Debian only has dependencies across packages, not on libraries. Actually I still wonder how smart could succeed here using a debian backend. I ignore if apt-rpm does support library dependencies.
While I can't verify this (not that familiar with the deb packaging), but if that is really true, it more or less explains why apt is faster than yum - they dont have much stuff to consider and process in the metadata. Yum+RPM can do dep check by libraries, files, executables, perl modules, and some other modules, which makes the metadata large, and depsolve requires more stuff to consider. So, APT-deb users, stop complaining YUM is slow (/me stares at ubuntu zombies) :P
Do tell me if that is wrong :)
On another note, Yaakov M. Nemoy wrote a very good post about why its not good to standardize to only 1 packaging system and package format across distributions.