I like KPackage, as far as a front end goes. It doesn't address the dependency or installation problems, but it makes it easier to see what's available for update and all that. Sometimes I think it's just a timing thing with package availability. Running apt today, it isn't trying to remove all the KDE stuff anymore.