e.g.: https://travis-ci.org/wikimedia/pywikibot-core/jobs/159508801
$ sudo -E apt-get -yq --no-install-suggests --no-install-recommends --force-yes install libssl1.0.0 djvulibre-bin liblua5.1-0-dev Reading package lists... Building dependency tree... Reading state information... The following packages were automatically installed and are no longer required: g++-4.6 git-man mysql-server-core-5.5 mysql-client-core-5.5 libstdc++6-4.6-dev libevent-2.0-5 Use 'apt-get autoremove' to remove them. The following extra packages will be installed: binutils cpp cpp-6 dbus dh-apparmor dpkg g++ g++-6 gcc gcc-6 gcc-6-base init-system-helpers libacl1 libapparmor1 libasan3 libatomic1 libattr1 libaudit-common libaudit1 libblkid1 libc-bin libc-dev-bin libc-l10n libc6 libc6-dev libcap-ng0 libcc1-0 libcilkrts5 libdbus-1-3 libdjvulibre-dev libdjvulibre-text libdjvulibre21 libfdisk1 libgcc-6-dev libgcc1 libgcrypt20 libgomp1 libgpg-error-dev libgpg-error0 libisl15 libitm1 libjbig0 libjpeg62-turbo liblocale-gettext-perl liblsan0 liblua5.1-0 liblzma-dev liblzma5 libmount1 libmpc3 libmpfr4 libmpx2 libncurses5 libncurses5-dev libncursesw5 libncursesw5-dev libnih-dbus1 libnih1 libquadmath0 libselinux1 libsmartcols1 libssl-dev libssl1.0.2 libstdc++-6-dev libstdc++6 libsystemd0 libtiff5 libtinfo-dev libtinfo5 libtsan0 libubsan0 libudev1 linux-libc-dev locales ncurses-bin perl-base sysvinit-utils tar util-linux ... Processing triggers for libc-bin ... ldconfig deferred processing now taking place Errors were encountered while processing: /var/cache/apt/archives/locales_2.24-2_all.deb ...
Note the existing precise-sudo and trusty images do not have this problem, and the trusty image is green.
The precise-sudo image has a different error:
https://travis-ci.org/jayvdb/pywikibot-core/jobs/164356420
$ sudo -E apt-get -yq --no-install-suggests --no-install-recommends --force-yes install libssl1.0.0 djvulibre-bin liblua5.1-0-dev Reading package lists... Building dependency tree... Reading state information... 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: util-linux : Breaks: cloud-utils (< 0.27-1~) but 0.25-0ubuntu5.1 is to be installed E: Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.
However resolving this by upgrading cloud-utils results in the same problem with locales.