Comment 4 for bug 68430

I'm currently looking into this issue. Only apt-get is affected, update-manager gets it with because it does post-processing after the runing cache.upgrade() (making sure that *buntu-desktop is still installed for example). And the aptitude resolver is different (and better) so this one gets it right too.

Unfortunately apt-get dist-upgrade does not get it right. The problem resolver says:

Investigating xserver-xorg-video-dummy
Package xserver-xorg-video-dummy has broken dep on xserver-xorg-driver-dummy
  Considering xserver-xorg-driver-dummy 1 as a solution to xserver-xorg-video-dummy 1
  Holding Back xserver-xorg-video-dummy rather than change xserver-xorg-driver-dummy

(this is the same for all the xserver-xorg-driver-$foo).

So it fails to replace the x-x-driver-$foo with the new x-x-video-$foo and this causes the problems. Unfortunately the fix does not help with this issue. Apt will remove xserver-xorg during the dist-upgrade (because it is first kept to the installed version and then later gets removed because x11-common in the new version conflicts with the old version).

So xserver-xorg-driver-$foo gets the same score from apt as x-x-video-$foo and in a situation apts problem resolver keeps the package. The score is generated by looking at the rdepends of the package, priority and installed package gets a point extra.