Did you follow the upgrade instructions? ISTR you're meant to use aptitude precisely because apt-get will do things like what you describe here...

No, because I didn't even know there were upgrade instructions in the release notes. apt-get dist-upgrade has always worked fine for me in the past, so I'd never previously had trouble from not reading release notes and it wasn't obvious that they were the first thing I should look for.

I'll read them now and see if they provide any useful information about how to sort out my remaining problems...

I really don't understand why they didn't improve the apt-get dependency algorithm instead of making a whole new tool with the same interface but cleverer magic.. (I'm aware aptitude also has a GUI, but why couldn't they have built it on top of apt-get in a nicer way?)

Until just now, I'd assumed that that was what they'd done. Gosh.