Please also note, tzhat there is a difference, between using apt (apt-get) and aptitude.
The way, I prefewr, is using apt-get upgrade (which installs only newer packages, and let the problematic ones uninstalled), then using apt-get full- upgrade. When there are packages deinstalled, reinstall them afterwards. I know, this is not the best way. As itr was mentioned before: Using aptitude (tzhe ncurses gui) can show you, which packages are causing trouble. You can set them to hold (aptitude hold packagename) and then analyse, what dependencies are causing the trouble. One package after the other. Yes, it is annoying, I agree. Hope this helps still.... Best regards Hans