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.