While attempting to upgrade to Ubuntu 11.10 (Oneiric) from 11.04, do-release-upgrade refused to do anything useful. The only message it felt like delivering was “E:Error, pkgProblemResolver::Resolve generated breaks”. Googling didn’t turn up much, but a forum thread (which I seem to have lost now) suggested (among other attempts) to remove any references to external (3rd party) APT repositories. I thought do-release-upgrade did this by itself, but apparently not …
Commenting out the external repositories in /etc/apt/sources.list and in /etc/apt/sources.list.d/* solved the problem (I had spotify, dropbox and Google Chrome there), allowing do-release-upgrade to do its thing.