Comment 11 for bug 987007

The earlier apt logs show:
Investigating (4) xserver-xorg-video-all [ amd64 ] < 1:7.6+7ubuntu7.1 -> 1:7.6+12ubuntu1 > ( x11 )
Broken xserver-xorg-video-all:amd64 Depends on xserver-xorg-video-ati [ amd64 ] < 1:6.14.99+git1109271105.a6b2bd~gd~n > ( x11 )
  Considering xserver-xorg-video-ati:amd64 10005 as a solution to xserver-xorg-video-all:amd64 10005
  Considering xserver-xorg-video-ati:amd64 10005 as a solution to xserver-xorg-video-all:amd64 10005
Broken xserver-xorg-video-all:amd64 Depends on xserver-xorg-video-nouveau [ amd64 ] < 1:0.0.16+git1108071527.b806e3~gd~n > ( x11 )
  Considering xserver-xorg-video-nouveau:amd64 10005 as a solution to xserver-xorg-video-all:amd64 10005
  Considering xserver-xorg-video-nouveau:amd64 10005 as a solution to xserver-xorg-video-all:amd64 10005
Done

This is the same as bug #974647: you have installed X drivers from a ppa which are not ABI-compatible with the X server in 12.04, but the version numbers are greater than the versions of the package available in 12.04, so apt cannot calculate an upgrade path.

I'm not sure how removing fglrx would have helped with this at all.