Comment 11 for bug 1318084

OK, I looked at 12.04.4 more closely, and it's a similar but not identical problem. The default saucy install includes libegl1-mesa-lts-saucy, but does NOT include libgles2-mesa-lts-saucy. Interestingly, trying to install glmark2-es2 by itself pulls the correct libgles2-mesa-lts-saucy:

$ sudo apt-get install glmark2-es2
The following extra packages will be installed:
  glmark2-data libgles2-mesa-lts-saucy

On the resolver I can see it doesn't want to install libgles:

Investigating (0) libgles2-mesa [ amd64 ] < none -> 8.0.4-0ubuntu0.7 > ( libs )
Broken libgles2-mesa:amd64 Depends on libglapi-mesa [ amd64 ] < none -> 8.0.4-0ubuntu0.7 > ( libs ) (= 8.0.4-0ubuntu0.7)
  Considering libglapi-mesa:amd64 0 as a solution to libgles2-mesa:amd64 1
  Holding Back libgles2-mesa:amd64 rather than change libglapi-mesa:amd64

eventually it decides to install the lts package:

Investigating (5) glmark2-es2 [ amd64 ] < none -> 2011.09-0ubuntu1 > ( universe/misc )
Broken glmark2-es2:amd64 Depends on libgles2-mesa [ amd64 ] < none -> 8.0.4-0ubuntu0.7 > ( libs ) (>= 7.8.1)
  Considering libgles2-mesa:amd64 1 as a solution to glmark2-es2:amd64 9999
  Considering libgles2-mesa:amd64 1 as a solution to glmark2-es2:amd64 9999
  Considering libgles2-mesa:amd64 1 as a solution to glmark2-es2:amd64 9999
Broken glmark2-es2:amd64 Depends on libgles2 [ amd64 ] < none > ( none )
  Considering libgles2-mesa-lts-raring:amd64 54 as a solution to glmark2-es2:amd64 9999
  Considering libgles2-mesa-lts-quantal:amd64 54 as a solution to glmark2-es2:amd64 9999
  Considering libgles2-mesa:amd64 1 as a solution to glmark2-es2:amd64 9999
  Considering libgles2-mesa-lts-trusty:amd64 0 as a solution to glmark2-es2:amd64 9999
  Considering libgles2-mesa-lts-saucy:amd64 0 as a solution to glmark2-es2:amd64 9999
  Re-Instated libgles2-mesa-lts-saucy:amd64

but when trying to install via plainbox-provider-certification-client, it wants to install libgles2-mesa. Apparently very early on in the problem solving process it decides it's OK to install libgles2-mesa at the expense of removing xorg:

Investigating (0) xserver-xorg-lts-saucy [ amd64 ] < 1:7.7+1ubuntu6~precise1 > ( x11 )
Broken xserver-xorg-lts-saucy:amd64 Conflicts on libgles2-mesa [ amd64 ] < none -> 8.0.4-0ubuntu0.7 > ( libs ) (>= 0~)
  Considering libgles2-mesa:amd64 0 as a solution to xserver-xorg-lts-saucy:amd64 0
  Removing xserver-xorg-lts-saucy:amd64 rather than change libgles2-mesa:amd64
Investigating (0) libgles2-mesa [ amd64 ] < none -> 8.0.4-0ubuntu0.7 > ( libs )
Broken libgles2-mesa:amd64 Depends on libglapi-mesa [ amd64 ] < none -> 8.0.4-0ubuntu0.7 > ( libs ) (= 8.0.4-0ubuntu0.7)
  Considering libglapi-mesa:amd64 0 as a solution to libgles2-mesa:amd64 0
  Holding Back libgles2-mesa:amd64 rather than change libglapi-mesa:amd64

This looks like a very obscure apt resolving bug :/ and the problem is, it only happens when glmark2-es2 is installed as a dependency, not when installed directly.