Comment 7 for bug 658581

I experienced that problem, too, but suddenly it worked - and I really do not know why!

I have got a ~5 year old computer with slow network connection running ubuntu lucid 10.04.1 (was upgraded from 10.04 via alternate CD)
When trying to upgrade to 10.10 with the alternate CD, I also received the error 'E:Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.'

Going through apt.log I found a lot of messages "Try to Re-Instate ...", most of them for xserver-xorg-video-... packages.
I had all possible xorg-video drivers installed (via xserver-xorg-video-all) and decided to remove all except -nv (which is the one I have enabled in Xorg.conf) and -vesa (for fallback).
Result: still the same error, but with a lower number of "Try to Re-Instate ..." messages in apt-log.

Next try: digging through program sources to find out who writes those messages -> seems apt
Checking release notes of apt shows that from 0.7.x (lucid) to 0.8.x (maverick) the messages in algorithms.cc have been extended to show more information in the pkgProblemResolver steps. Thought it could be a good idea to update to the latest (maverick) release and try again, hopefully receiving more indications.
Downloaded apt_0.8.3ubuntu7_i386.deb and installed with package manager (message: "all dependencies satisfied"), but alas, this broke almost all apt and synaptic packages because apt 0.8 is no longer providing libapt-pkg-libc6.10-6-4.8 but libapt-pkg4.10 (still have to check if I should report a bug about that).
apt-get install -f wanted to remove lots of packages (which I refused)
So back, installed apt_0.7.25.3ubuntu9.3_i386.deb via dpkg.
Happy to see that apt-get install -f did not show any problems any more.

Next try: could my system be upgraded to 10.10 via network download?
started update-manager to upgrade via network -> and it was able to resolve the dependencies and asked me if it should really start the upgrade. (estimated download time 7 hours for files that I already have on CD, so I decided to abort). apt.log did not show any "Try to Re-Instate ..." lines.

Synaptic told me that there are half a dozen new erlang... packages available, so I installed these updates.

Next try: back to the alternate cd, with the idea to enable debug messages as much as possible. Created an apt.conf with several Debug::xxx "true".
What can I tell: sudo sh /media/Ubuntu 10.10/cdromupgrade worked!
Now apparently it was able to resolve the dependencies and asked me if it should really start the upgrade. (decided to cancel because it was already late in the evening, and I wanted to keep the possibility to try to chase this bug further).
Again apt.log did not show any "Try to Re-Instate ..." lines.

Tried again without Debug enabled, and it worked again -> so seems not caused by debug enabled.

What I do not know now is which step in my attempts is the one that is responsible that it works now (up-/downgrading apt, installing erlang..., trying to upgrade over the network once, ...).

What I suspect is that the appearence of "Try to Re-Instate ..." lines in apt.log leads to the 'E:Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.' message. All apt.log files of failed upgrades in launchpad bugs that I looked at have those. Maybe mvo can shed some light on that?
What I also could think of is that the number of dependencies and conflicts to resolve at my first attempts was too high, and reducing the number of dependencies/conflicts (by removing xorg-video-... and upgrading erlang...) was the key.

Sorry for the lengthy post, but I thought I should add all the information that possibly could help to find the cause of the bug (and maybe a solution).
I am willing to do some more tries on my system.

regards, MH