apt-get dist-upgrade tries to remove the following packages:and upgrade rather than dist-upgrade? Try using aptitude instead of apt. It sometimes does a better job, and just 'aptitude' so you get the curses interface makes it _much_ easier to track down what's actually up. 'B' shows broken packages which is often a clue.
I've tried and it offered me 100500 different insane ways of solving the situation... :) that's why I don't use it, its solver seems really insane. apt-get is far more rational :)
The single thing that I found aptitude useful for is finding and removing packages that are unavailable in current debian release anymore :)
-- With best regards, Vitaliy Filippov