As a result of the LTS enablement work in 12.04.2, we now have a situation where for the first time, a library dependency of a substantial number of packages in main is satisfied by two different real packages (libgl1-mesa-glx-lts-quantal Provides: libgl1-mesa-glx), and there isn't one right "default" answer to the question of which package should be installed (users who installed 12.04 have one option; users who installed 12.04.2 have a different one). This interacts quite badly with apt's resolver when cross-installing a multiarch-capable package that also has a dependency on one of these libraries. For example, the steam:i386 package has the following dependencies: Depends: libc6, libgl1-mesa-dri, libgl1-mesa-glx, xterm | gnome-terminal, zenity Since libgl1-mesa-dri and libgl1-mesa-glx are both real packages, apt tries to pull these in by name. However, the libgl1-mesa-glx-lts-quantal:amd64 and libgl1-mesa-dri-lts-quantal:amd64 packages already installed have a Conflicts/Provides on libgl1-mesa-glx and libgl1-mesa-dri respectively, and the conflicts relationship crosses architectures. It's reported that when installing via software-center, this conflict may even result in removal of the X server. I can't reproduce this myself (since steam64 has now been withdrawn from the software center until the problem can be addressed), but apt is certainly not able to find a solution to this problem on its own: sudo apt-get -o Debug::pkgProblemResolver=1 install steam Reading package lists... Done Building dependency tree Reading state information... Done Starting Starting 2 Investigating (0) libgl1-mesa-dri-lts-quantal [ amd64 ] < 9.0-0ubuntu1~precise4 > ( libs ) Broken libgl1-mesa-dri-lts-quantal:amd64 Conflicts on libgl1-mesa-dri [ i386 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Considering libgl1-mesa-dri:i386 2 as a solution to libgl1-mesa-dri-lts-quantal:amd64 33 Added libgl1-mesa-dri:i386 to the remove list Conflicts//Breaks against version 8.0.4-0ubuntu0.2 for libgl1-mesa-dri but that is not InstVer, ignoring Conflicts//Breaks against version 8.0.2-0ubuntu3 for libgl1-mesa-dri but that is not InstVer, ignoring Fixing libgl1-mesa-dri-lts-quantal:amd64 via keep of libgl1-mesa-dri:i386 Investigating (0) libgnome-desktop-3-2 [ amd64 ] < 3.4.2-0ubuntu0.1 > ( libs ) Broken libgnome-desktop-3-2:amd64 Depends on libgl1-mesa-glx [ amd64 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Considering libgl1-mesa-glx:amd64 14 as a solution to libgnome-desktop-3-2:amd64 30 Added libgl1-mesa-glx:amd64 to the remove list Broken libgnome-desktop-3-2:amd64 Depends on libgl1 [ amd64 ] < none > ( none ) Considering libgl1-mesa-swx11:amd64 0 as a solution to libgnome-desktop-3-2:amd64 30 Added libgl1-mesa-swx11:amd64 to the remove list Fixing libgnome-desktop-3-2:amd64 via keep of libgl1-mesa-glx:amd64 Fixing libgnome-desktop-3-2:amd64 via keep of libgl1-mesa-swx11:amd64 Investigating (0) gnome-session-bin [ amd64 ] < 3.2.1-0ubuntu8 > ( gnome ) Broken gnome-session-bin:amd64 Depends on libgl1-mesa-glx [ amd64 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Considering libgl1-mesa-glx:amd64 14 as a solution to gnome-session-bin:amd64 17 Added libgl1-mesa-glx:amd64 to the remove list Broken gnome-session-bin:amd64 Depends on libgl1 [ amd64 ] < none > ( none ) Considering libgl1-mesa-swx11:amd64 0 as a solution to gnome-session-bin:amd64 17 Added libgl1-mesa-swx11:amd64 to the remove list Fixing gnome-session-bin:amd64 via keep of libgl1-mesa-glx:amd64 Fixing gnome-session-bin:amd64 via keep of libgl1-mesa-swx11:amd64 Investigating (0) x11-utils [ amd64 ] < 7.6+4ubuntu0.1 > ( x11 ) Broken x11-utils:amd64 Depends on libgl1-mesa-glx [ amd64 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Considering libgl1-mesa-glx:amd64 14 as a solution to x11-utils:amd64 16 Added libgl1-mesa-glx:amd64 to the remove list Broken x11-utils:amd64 Depends on libgl1 [ amd64 ] < none > ( none ) Considering libgl1-mesa-swx11:amd64 0 as a solution to x11-utils:amd64 16 Added libgl1-mesa-swx11:amd64 to the remove list Fixing x11-utils:amd64 via keep of libgl1-mesa-glx:amd64 Fixing x11-utils:amd64 via keep of libgl1-mesa-swx11:amd64 Investigating (0) libnux-2.0-0 [ amd64 ] < 2.14.1-0ubuntu1 > ( libs ) Broken libnux-2.0-0:amd64 Depends on libgl1-mesa-glx [ amd64 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Considering libgl1-mesa-glx:amd64 14 as a solution to libnux-2.0-0:amd64 12 Try Installing libgl1-mesa-glx [ amd64 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) before changing libnux-2.0-0:amd64 Investigating (0) libglapi-mesa-lts-quantal [ amd64 ] < 9.0-0ubuntu1~precise4 > ( libs ) Broken libglapi-mesa-lts-quantal:amd64 Conflicts on libglapi-mesa [ amd64 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Considering libglapi-mesa:amd64 0 as a solution to libglapi-mesa-lts-quantal:amd64 5 Added libglapi-mesa:amd64 to the remove list Conflicts//Breaks against version 8.0.4-0ubuntu0.2 for libglapi-mesa but that is not InstVer, ignoring Conflicts//Breaks against version 8.0.2-0ubuntu3 for libglapi-mesa but that is not InstVer, ignoring Broken libglapi-mesa-lts-quantal:amd64 Conflicts on libglapi-mesa [ i386 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Considering libglapi-mesa:i386 0 as a solution to libglapi-mesa-lts-quantal:amd64 5 Added libglapi-mesa:i386 to the remove list Conflicts//Breaks against version 8.0.4-0ubuntu0.2 for libglapi-mesa but that is not InstVer, ignoring Conflicts//Breaks against version 8.0.2-0ubuntu3 for libglapi-mesa but that is not InstVer, ignoring Fixing libglapi-mesa-lts-quantal:amd64 via keep of libglapi-mesa:amd64 Fixing libglapi-mesa-lts-quantal:amd64 via keep of libglapi-mesa:i386 Investigating (0) libqt4-opengl [ amd64 ] < 4:4.8.1-0ubuntu4.3 -> 4:4.8.1-0ubuntu4.4 > ( libs ) Broken libqt4-opengl:amd64 Depends on libqtcore4 [ amd64 ] < 4:4.8.1-0ubuntu4.3 -> 4:4.8.1-0ubuntu4.4 > ( libs ) (= 4:4.8.1-0ubuntu4.4) Considering libqtcore4:amd64 93 as a solution to libqt4-opengl:amd64 4 Holding Back libqt4-opengl:amd64 rather than change libqtcore4:amd64 Investigating (0) libgl1-mesa-glx [ i386 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Broken libgl1-mesa-glx:i386 Depends on libglapi-mesa [ i386 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) (= 8.0.4-0ubuntu0.3) Considering libglapi-mesa:i386 0 as a solution to libgl1-mesa-glx:i386 1 Holding Back libgl1-mesa-glx:i386 rather than change libglapi-mesa:i386 Investigating (0) xserver-xorg-lts-quantal [ amd64 ] < 1:7.7+1ubuntu4~precise1 > ( x11 ) Broken xserver-xorg-lts-quantal:amd64 Conflicts on libgl1-mesa-dri [ amd64 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) (>= 0~) Considering libgl1-mesa-dri:amd64 1 as a solution to xserver-xorg-lts-quantal:amd64 0 Removing xserver-xorg-lts-quantal:amd64 rather than change libgl1-mesa-dri:amd64 Investigating (1) steam [ i386 ] < none -> 1.0.0.27ubuntu1 > ( games ) Broken steam:i386 Depends on libgl1-mesa-dri [ i386 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Considering libgl1-mesa-dri:i386 2 as a solution to steam:i386 9999 Re-Instated libgl1-mesa-dri:i386 Broken steam:i386 Depends on libgl1-mesa-glx [ i386 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Considering libgl1-mesa-glx:i386 1 as a solution to steam:i386 9999 Re-Instated libglapi-mesa:i386 Re-Instated libgl1-mesa-glx:i386 Investigating (1) libgl1-mesa-dri-lts-quantal [ amd64 ] < 9.0-0ubuntu1~precise4 > ( libs ) Broken libgl1-mesa-dri-lts-quantal:amd64 Conflicts on libgl1-mesa-dri [ amd64 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Considering libgl1-mesa-dri:amd64 1 as a solution to libgl1-mesa-dri-lts-quantal:amd64 33 Added libgl1-mesa-dri:amd64 to the remove list Conflicts//Breaks against version 8.0.4-0ubuntu0.2 for libgl1-mesa-dri but that is not InstVer, ignoring Conflicts//Breaks against version 8.0.2-0ubuntu3 for libgl1-mesa-dri but that is not InstVer, ignoring Broken libgl1-mesa-dri-lts-quantal:amd64 Conflicts on libgl1-mesa-dri [ i386 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Considering libgl1-mesa-dri:i386 2 as a solution to libgl1-mesa-dri-lts-quantal:amd64 33 Added libgl1-mesa-dri:i386 to the remove list Conflicts//Breaks against version 8.0.4-0ubuntu0.2 for libgl1-mesa-dri but that is not InstVer, ignoring Conflicts//Breaks against version 8.0.2-0ubuntu3 for libgl1-mesa-dri but that is not InstVer, ignoring Fixing libgl1-mesa-dri-lts-quantal:amd64 via keep of libgl1-mesa-dri:amd64 Fixing libgl1-mesa-dri-lts-quantal:amd64 via keep of libgl1-mesa-dri:i386 Investigating (1) libgl1-mesa-glx [ amd64 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Broken libgl1-mesa-glx:amd64 Depends on libglapi-mesa [ amd64 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) (= 8.0.4-0ubuntu0.3) Considering libglapi-mesa:amd64 0 as a solution to libgl1-mesa-glx:amd64 14 Holding Back libgl1-mesa-glx:amd64 rather than change libglapi-mesa:amd64 Investigating (1) libnux-2.0-0 [ amd64 ] < 2.14.1-0ubuntu1 > ( libs ) Broken libnux-2.0-0:amd64 Depends on libgl1-mesa-glx [ amd64 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Considering libgl1-mesa-glx:amd64 14 as a solution to libnux-2.0-0:amd64 12 Try Installing libgl1-mesa-glx [ amd64 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) before changing libnux-2.0-0:amd64 Investigating (1) libglapi-mesa-lts-quantal [ amd64 ] < 9.0-0ubuntu1~precise4 > ( libs ) Broken libglapi-mesa-lts-quantal:amd64 Conflicts on libglapi-mesa [ amd64 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Considering libglapi-mesa:amd64 0 as a solution to libglapi-mesa-lts-quantal:amd64 5 Added libglapi-mesa:amd64 to the remove list Conflicts//Breaks against version 8.0.4-0ubuntu0.2 for libglapi-mesa but that is not InstVer, ignoring Conflicts//Breaks against version 8.0.2-0ubuntu3 for libglapi-mesa but that is not InstVer, ignoring Broken libglapi-mesa-lts-quantal:amd64 Conflicts on libglapi-mesa [ i386 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Considering libglapi-mesa:i386 0 as a solution to libglapi-mesa-lts-quantal:amd64 5 Added libglapi-mesa:i386 to the remove list Conflicts//Breaks against version 8.0.4-0ubuntu0.2 for libglapi-mesa but that is not InstVer, ignoring Conflicts//Breaks against version 8.0.2-0ubuntu3 for libglapi-mesa but that is not InstVer, ignoring Fixing libglapi-mesa-lts-quantal:amd64 via keep of libglapi-mesa:amd64 Fixing libglapi-mesa-lts-quantal:amd64 via keep of libglapi-mesa:i386 Try to Re-Instate (1) libqt4-opengl:amd64 Investigating (1) libgl1-mesa-glx [ i386 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Broken libgl1-mesa-glx:i386 Depends on libglapi-mesa [ i386 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) (= 8.0.4-0ubuntu0.3) Considering libglapi-mesa:i386 0 as a solution to libgl1-mesa-glx:i386 1 Holding Back libgl1-mesa-glx:i386 rather than change libglapi-mesa:i386 Investigating (1) xorg [ amd64 ] < 1:7.6+12ubuntu2 > ( x11 ) Broken xorg:amd64 Depends on xserver-xorg [ amd64 ] < none -> 1:7.6+12ubuntu2 > ( x11 ) (>= 1:7.6+12ubuntu2) Considering xserver-xorg:amd64 3 as a solution to xorg:amd64 1 Try Installing xserver-xorg [ amd64 ] < none -> 1:7.6+12ubuntu2 > ( x11 ) before changing xorg:amd64 Broken xorg:amd64 Depends on xserver-xorg-renamed [ amd64 ] < none > ( none ) Considering xserver-xorg-lts-quantal:amd64 0 as a solution to xorg:amd64 1 Added xserver-xorg-lts-quantal:amd64 to the remove list Fixing xorg:amd64 via keep of xserver-xorg-lts-quantal:amd64 Investigating (1) xserver-xorg-lts-quantal [ amd64 ] < 1:7.7+1ubuntu4~precise1 > ( x11 ) Broken xserver-xorg-lts-quantal:amd64 Depends on xserver-xorg-core-lts-quantal [ amd64 ] < 2:1.13.0-0ubuntu6.1~precise2 > ( x11 ) (>= 2:1.11) Considering xserver-xorg-core-lts-quantal:amd64 54 as a solution to xserver-xorg-lts-quantal:amd64 0 Removing xserver-xorg-lts-quantal:amd64 rather than change xserver-xorg-core-lts-quantal:amd64 Investigating (2) steam [ i386 ] < none -> 1.0.0.27ubuntu1 > ( games ) Broken steam:i386 Depends on libgl1-mesa-dri [ i386 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Considering libgl1-mesa-dri:i386 2 as a solution to steam:i386 9999 Considering libgl1-mesa-dri:i386 2 as a solution to steam:i386 9999 Considering libgl1-mesa-dri:i386 2 as a solution to steam:i386 9999 Considering libgl1-mesa-dri-lts-quantal:i386 0 as a solution to steam:i386 9999 Re-Instated libdrm-nouveau2:i386 Re-Instated libglapi-mesa-lts-quantal:i386 Re-Instated libllvm3.1:i386 Re-Instated libgl1-mesa-dri-lts-quantal:i386 Broken steam:i386 Depends on libgl1-mesa-glx [ i386 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Considering libgl1-mesa-glx:i386 1 as a solution to steam:i386 9999 Considering libgl1-mesa-glx:i386 1 as a solution to steam:i386 9999 Considering libgl1-mesa-glx:i386 1 as a solution to steam:i386 9999 Considering libgl1-mesa-glx-lts-quantal:i386 0 as a solution to steam:i386 9999 Re-Instated libgl1-mesa-glx-lts-quantal:i386 Investigating (2) libgl1-mesa-glx [ amd64 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Broken libgl1-mesa-glx:amd64 Depends on libglapi-mesa [ amd64 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) (= 8.0.4-0ubuntu0.3) Considering libglapi-mesa:amd64 0 as a solution to libgl1-mesa-glx:amd64 14 Holding Back libgl1-mesa-glx:amd64 rather than change libglapi-mesa:amd64 Investigating (2) libnux-2.0-0 [ amd64 ] < 2.14.1-0ubuntu1 > ( libs ) Broken libnux-2.0-0:amd64 Depends on libgl1-mesa-glx [ amd64 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Considering libgl1-mesa-glx:amd64 14 as a solution to libnux-2.0-0:amd64 12 Try Installing libgl1-mesa-glx [ amd64 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) before changing libnux-2.0-0:amd64 Investigating (2) xorg [ amd64 ] < 1:7.6+12ubuntu2 > ( x11 ) Broken xorg:amd64 Depends on xserver-xorg [ amd64 ] < none -> 1:7.6+12ubuntu2 > ( x11 ) (>= 1:7.6+12ubuntu2) Considering xserver-xorg:amd64 3 as a solution to xorg:amd64 1 Try Installing xserver-xorg [ amd64 ] < none -> 1:7.6+12ubuntu2 > ( x11 ) before changing xorg:amd64 Investigating (3) steam [ i386 ] < none -> 1.0.0.27ubuntu1 > ( games ) Broken steam:i386 Depends on libgl1-mesa-dri [ i386 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Considering libgl1-mesa-dri:i386 2 as a solution to steam:i386 9999 Considering libgl1-mesa-dri:i386 2 as a solution to steam:i386 9999 Considering libgl1-mesa-dri:i386 2 as a solution to steam:i386 9999 Considering libgl1-mesa-dri-lts-quantal:i386 0 as a solution to steam:i386 9999 Broken steam:i386 Depends on libgl1-mesa-glx [ i386 ] < none -> 8.0.4-0ubuntu0.3 > ( libs ) Considering libgl1-mesa-glx:i386 1 as a solution to steam:i386 9999 Considering libgl1-mesa-glx:i386 1 as a solution to steam:i386 9999 Considering libgl1-mesa-glx:i386 1 as a solution to steam:i386 9999 Considering libgl1-mesa-glx-lts-quantal:i386 0 as a solution to steam:i386 9999 Done Some packages could not be installed. This may mean that you have requested an impossible situation or if you are using the unstable distribution that some required packages have not yet been created or been moved out of Incoming. The following information may help to resolve the situation: The following packages have unmet dependencies: steam:i386 : Depends: libgl1-mesa-dri:i386 Depends: libgl1-mesa-glx:i386 E: Unable to correct problems, you have held broken packages. Getting a correct result requires the following: $ sudo apt-get install libgl1-mesa-dri-lts-quantal:i386 libglapi-mesa-lts-quantal:i386 libgl1-mesa-glx-lts-quantal:i386 steam Since we don't have enough information to say with certainty that all Conflicts from packages of a different architecture can be ignored, it seems we need apt's resolver to be smarter, and possibly give priority to implementors of virtual packages that are already installed for a different architecture when trying to satisfy dependencies.