The aptitude removal is probably due to C++ ABI transitions: since SONAMEs don't typically capture the C++ ABI, C++ library filenames have to stay the same, but the package name has to change in order that the packaging system knows how (not) to do partial upgrades; this means that we end up with post-transition C++ library packages that conflict with pre-transition ones. Put this together with whoever thought it was a good idea to write package managers in C++, with apt being a little too unwilling to leave broken packages around on the system while their dependencies are being shuffled (although that might not have made a difference - you could still have ended up with aptitude being there but not some of the libraries against which it was linked), and probably with the X.org transition causing the upgrade to fail, and you end up with your mess.

I think the answer is likely to be to simplify the dependency web around aptitude.