My addition: trying a respin of Ubuntu 10.04 on a blank x86_64 system.
The same error comes shortly after installing the system and
removing/adding a few packages. Reinstall of xorg-server-video-all and
xorg-server-input-all does not help. Thus the problem seems to have
deeper roots in the past
To be continued: apparently my particular problem came from switching to
maverick repository and upgrading some packages to 10.10 versions.
Disabling it a temporal solution.
--
E:Error, pkgProblemResolver::Resolve generated breaks, this may be caused by
held packages.