Upgrade from 14.04 to 15.04 fails

[tobyS]

We tried do-release-upgrade on a 14.04 machine today multiple times with all the same error. There are no held packages and everything is up to date for the old release. Error is:

----
Hit http://security.ubuntu.com vivid-security/universe Translation-en
Fetched 0 B in 0s (0 B/s)

Checking package manager
Reading package lists... Done
Building dependency tree
Reading state information... Done
Building data structures... Done

Calculating the changes

Calculating the changes

Could not calculate the upgrade

An unresolvable problem occurred while calculating the upgrade.

This can be caused by:
* Upgrading to a pre-release version of Ubuntu
* Running the current pre-release version of Ubuntu
* Unofficial software packages not provided by Ubuntu

If none of this applies, then please report this bug using the
command 'ubuntu-bug ubuntu-release-upgrader-core' in a terminal.

Restoring original system state
…
----

/var/log/dist-upgrade/main.log shows
----
2016-01-14 21:43:23,025 DEBUG /openCache(), new cache size 76304
2016-01-14 21:43:23,025 DEBUG need_server_mode(): run in 'desktop' mode, (because of pkg 'ubuntu-desktop')
2016-01-14 21:43:25,259 ERROR Dist-upgrade failed: 'E:Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.'
2016-01-14 21:43:25,260 DEBUG abort called
----

Thanks for any support in advance.

ProblemType: Bug
DistroRelease: Ubuntu 14.04
Package: ubuntu-release-upgrader-core 1:0.220.8
ProcVersionSignature: Ubuntu 3.13.0-74.118-generic 3.13.11-ckt30
Uname: Linux 3.13.0-74-generic x86_64
ApportVersion: 2.14.1-0ubuntu3.19
Architecture: amd64
CrashDB: ubuntu
CurrentDesktop: GNOME
Date: Thu Jan 14 21:43:40 2016
InstallationDate: Installed on 2014-06-10 (583 days ago)
InstallationMedia: Ubuntu 14.04 LTS "Trusty Tahr" - Release amd64 (20140417)
PackageArchitecture: all
SourcePackage: ubuntu-release-upgrader
UpgradeStatus: Upgraded to trusty on 2016-01-14 (0 days ago)
mtime.conffile..etc.update.manager.release.upgrades: 2016-01-14T20:50:42.707736