OK, a suitable workaround is to install glmark2-es2 prior to installing plainbox-provider-certification-client. For some reason still to be determined, installing that first correctly finds the saucy-stack dependency: $ sudo apt-get install glmark2-es2 Reading package lists... Done Building dependency tree Reading state information... Done The following extra packages will be installed: glmark2-data libgles2-mesa-lts-saucy The following NEW packages will be installed: glmark2-data glmark2-es2 libgles2-mesa-lts-saucy 0 upgraded, 3 newly installed, 0 to remove and 0 not upgraded. then the install of the provider doesn't remove any packages: $ sudo apt-get install plainbox-provider-certification-client Reading package lists... Done Building dependency tree Reading state information... Done The following package was automatically installed and is no longer required: python-dateutil Use 'apt-get autoremove' to remove them. The following extra packages will be installed: bonnie++ bootchart checkbox-ng checkbox-ng-service curl dkms ethtool fakeroot fswebcam fwts fwts-efi-runtime-dkms glmark2 gtkperf heirloom-mailx imagemagick imagemagick-common libbfb0 libbonobo2-0 libbonobo2-common libbonoboui2-0 libbonoboui2-common libcdt4 libcommon-sense-perl libencode-locale-perl libextutils-depends-perl libextutils-pkgconfig-perl libfile-listing-perl libfile-which-perl libfont-afm-perl libfwts1 libfwtsacpica1 libfwtsiasl1 libgif4 libglade2-0 libgnome2-0 libgnome2-bin libgnome2-canvas-perl libgnome2-gconf-perl libgnome2-perl libgnome2-vfs-perl libgnome2-wnck-perl libgnomecanvas2-0 libgnomecanvas2-common libgnomeui-0 libgnomeui-common libgnomevfs2-0 libgnomevfs2-common libgnomevfs2-extra libgoo-canvas-perl libgoocanvas-common libgoocanvas3 libgraph4 libgsm1 libgtk2-imageview-perl libgtk2-unique-perl libgtkimageview0 libgvc5 libhtml-form-perl libhtml-format-perl libhtml-parser-perl libhtml-tagset-perl libhtml-tree-perl libhttp-cookies-perl libhttp-daemon-perl libhttp-date-perl libhttp-message-perl libhttp-negotiate-perl libhttp-server-simple-perl libid3tag0 libidl-common libidl0 libilmbase6 libimlib2 libio-socket-inet6-perl libio-socket-ssl-perl libjson-perl libjson-xs-perl liblqr-1-0 liblwp-mediatypes-perl liblwp-protocol-https-perl libmagickcore4 libmagickcore4-extra libmagickwand4 libmailtools-perl libmulticobex1 libnet-dbus-perl libnet-http-perl libnet-ssleay-perl libnetpbm10 libobexftp0 libopencore-amrnb0 libopencore-amrwb0 libopenexr6 liborbit2 libpath-class-perl libpathplan4 libproc-processtable-perl libproc-simple-perl libsocket6-perl libsort-naturally-perl libsox-fmt-alsa libsox-fmt-base libsox1b libtie-ixhash-perl libtimedate-perl libunique-1.0-0 liburi-perl libwww-mechanize-perl libwww-perl libwww-robotrules-perl libx11-protocol-perl libxml-namespacesupport-perl libxml-parser-perl libxml-sax-base-perl libxml-sax-expat-perl libxml-sax-perl libxml-simple-perl libxml-twig-perl libxml-xpath-perl netpbm nmap obexftp perlmagick plainbox-provider-checkbox plainbox-provider-resource-generic plainbox-secure-policy pybootchartgui python-support python3-chardet python3-checkbox-ng python3-checkbox-support python3-pkg-resources python3-plainbox python3-pyparsing python3-requests python3-six python3-urllib3 python3-xlsxwriter render-bench shutter smartmontools sox stress sysstat wmctrl Suggested packages: exim4 mail-transport-agent imagemagick-doc autotrace enscript ffmpeg gimp gnuplot grads hp2xx html2ps libwmf-bin mplayer povray radiance texlive-base-bin transfig ufraw-batch libbonobo2-bin libgnomevfs2-bin gamin fam gnome-mime-data libdata-dump-perl libcrypt-ssleay-perl libsox-fmt-all libauthen-ntlm-perl libunicode-map8-perl libunicode-string-perl xml-twig-tools python3-setuptools gnome-web-photo libnet-dropbox-api-perl libimage-exiftool-perl libnet-dbus-glib-perl gsmartcontrol smart-notifier isag Recommended packages: mailx mailutils The following NEW packages will be installed: bonnie++ bootchart checkbox-ng checkbox-ng-service curl dkms ethtool fakeroot fswebcam fwts fwts-efi-runtime-dkms glmark2 gtkperf heirloom-mailx imagemagick imagemagick-common libbfb0 libbonobo2-0 libbonobo2-common libbonoboui2-0 libbonoboui2-common libcdt4 libcommon-sense-perl libencode-locale-perl libextutils-depends-perl libextutils-pkgconfig-perl libfile-listing-perl libfile-which-perl libfont-afm-perl libfwts1 libfwtsacpica1 libfwtsiasl1 libgif4 libglade2-0 libgnome2-0 libgnome2-bin libgnome2-canvas-perl libgnome2-gconf-perl libgnome2-perl libgnome2-vfs-perl libgnome2-wnck-perl libgnomecanvas2-0 libgnomecanvas2-common libgnomeui-0 libgnomeui-common libgnomevfs2-0 libgnomevfs2-common libgnomevfs2-extra libgoo-canvas-perl libgoocanvas-common libgoocanvas3 libgraph4 libgsm1 libgtk2-imageview-perl libgtk2-unique-perl libgtkimageview0 libgvc5 libhtml-form-perl libhtml-format-perl libhtml-parser-perl libhtml-tagset-perl libhtml-tree-perl libhttp-cookies-perl libhttp-daemon-perl libhttp-date-perl libhttp-message-perl libhttp-negotiate-perl libhttp-server-simple-perl libid3tag0 libidl-common libidl0 libilmbase6 libimlib2 libio-socket-inet6-perl libio-socket-ssl-perl libjson-perl libjson-xs-perl liblqr-1-0 liblwp-mediatypes-perl liblwp-protocol-https-perl libmagickcore4 libmagickcore4-extra libmagickwand4 libmailtools-perl libmulticobex1 libnet-dbus-perl libnet-http-perl libnet-ssleay-perl libnetpbm10 libobexftp0 libopencore-amrnb0 libopencore-amrwb0 libopenexr6 liborbit2 libpath-class-perl libpathplan4 libproc-processtable-perl libproc-simple-perl libsocket6-perl libsort-naturally-perl libsox-fmt-alsa libsox-fmt-base libsox1b libtie-ixhash-perl libtimedate-perl libunique-1.0-0 liburi-perl libwww-mechanize-perl libwww-perl libwww-robotrules-perl libx11-protocol-perl libxml-namespacesupport-perl libxml-parser-perl libxml-sax-base-perl libxml-sax-expat-perl libxml-sax-perl libxml-simple-perl libxml-twig-perl libxml-xpath-perl netpbm nmap obexftp perlmagick plainbox-provider-certification-client plainbox-provider-checkbox plainbox-provider-resource-generic plainbox-secure-policy pybootchartgui python-support python3-chardet python3-checkbox-ng python3-checkbox-support python3-pkg-resources python3-plainbox python3-pyparsing python3-requests python3-six python3-urllib3 python3-xlsxwriter render-bench shutter smartmontools sox stress sysstat wmctrl 0 upgraded, 146 newly installed, 0 to remove and 0 not upgraded. I'll patch this in checkbox-satellite for a quick fix, but I still want to find out what's wrong with apt-get. I can try to produce a dummy minimal package that only depends on glmark2-es2 to see if the problem is somewhere in apt dependency resolution.