this may not be the answer you were looking for, but i think i had a lot of the same problems you did. i had some other distro (mdk 9.0) that demanded a whole bunch of dependencies concerning libraries that weren't installed. i found this immensely irritating, so i tried slackware, as people claimed it was reliable and stable.
lo and behold, it was. it's the best choice i've made in the past 6 months. with a minimal install of slack 9, i never have any problems with dependencies.