Comment 1 for bug 1511875

I encountered a similar problem when upgrading a container from 13.04 to 13.10.

The problem was that the listed dependencies for ubuntu-release-upgrader-core were not sufficient.

The solution was to install python-apt. (Even that was a bit difficult; I had to manually create an empty file, /etc/python2.7/sitecustomize.py).

If python-apt doesn't solve the problem, then you could try searching for other missing dependencies. Here's one way to do that:

(1) List the reverse-dependencies of ubuntu-release-upgrader-core:

apt-cache rdepends ubuntu-release-upgrader-core

On ubuntu-14.04 the reverse-dependencies include update-manager-core.

(2) List the dependencies of update-manager-core,

apt-cache depends update-manager-core

Try installing some or all of these dependencies and see whether it solves the problem.