What about using Smart in ubuntu hoary by default? I am using it in warty and it works nicely (I found a bug in inserting new channels using the gui, but besides that...). It resolves problems installing packages that apt/synaptic can't handle. Maybe it would be a good idea, it is made in python and C. What is you opinion?
ps. If someone thinks it is dificult to install it I will give some more indepth help, but basically you need gcc and python-dev. Then execute python setup.py install, and then to insert a new channel you have to read the docs, but you need at least one deb-sys channel.