Environment deployment fails: 'err: heat-api-cloudwatch : Depends: heat-common (= 2014.1.5-0ubuntu1) but it is not going to be installed'

Fuel version info (8.0 build #57): http://paste.openstack.org/show/477116/

Environment deployment fails because heat couldn't be installed due to dependency hell:

node-1 2015-10-22T09:25:43.349344 err: Execution of '/usr/bin/apt-get -q -y -o DPkg::Options::=--force-confold install heat-docker' returned 100: Reading package lists...
node-1 2015-10-22T09:25:43.349344 err: Building dependency tree...
node-1 2015-10-22T09:25:43.349344 err: Reading state information...
node-1 2015-10-22T09:25:43.349344 err: E: Unable to locate package heat-docker
...
node-1 2015-10-22T09:25:43.837980 err: Execution of '/usr/bin/apt-get -q -y -o DPkg::Options::=--force-confold install heat-api-cloudwatch' returned 100: Reading package lists...
node-1 2015-10-22T09:25:43.837980 err: Building dependency tree...
node-1 2015-10-22T09:25:43.837980 err: Reading state information...
node-1 2015-10-22T09:25:43.837980 err: Some packages could not be installed. This may mean that you have
node-1 2015-10-22T09:25:43.837980 err: requested an impossible situation or if you are using the unstable
node-1 2015-10-22T09:25:43.837980 err: distribution that some required packages have not yet been created
node-1 2015-10-22T09:25:43.837980 err: or been moved out of Incoming.
node-1 2015-10-22T09:25:43.838219 err: The following information may help to resolve the situation:
node-1 2015-10-22T09:25:43.838219 err:
node-1 2015-10-22T09:25:43.838219 err: The following packages have unmet dependencies:
node-1 2015-10-22T09:25:43.838219 err: heat-api-cloudwatch : Depends: heat-common (= 2014.1.5-0ubuntu1) but it is not going to be installed
node-1 2015-10-22T09:25:43.839263 err: E: Unable to correct problems, you have held broken packages.

http://paste.openstack.org/show/477117/

Diagnostic snapshot is attached.