Comment 2 for bug 1525361

Ok. I've reproduced this, and collected some info here.
First, the following is a bit simpler user data to reproduce:
  #!/bin/bash
  exec >/run/docker.install.out 2>&1 </dev/null
  set -x
  export http_proxy=http://squid.internal:3128
  export DEBIAN_FRONTEND=noninteractive
  apt-key adv --keyserver hkp://p80.pool.sks-keyservers.net:80 --recv-keys 58118E89F3A912897C070ADBF76221572C52609D
  echo "deb https://apt.dockerproject.org/repo ubuntu-wily main" > /etc/apt/sources.list.d/docker.list
  apt-get update
  apt-get install -y docker-engine

The changes there are that cloud-init is executing as root, so no need for beign root. Second is that I just put all output to /run/docker.install.out. I've added the http_proxy for my own environment where that is needed.

And just an FYI, a similar cloud-config to accomplish the above looks like. It also reproduces the issue.
  #cloud-config
  apt_sources:
   - source: "deb https://apt.dockerproject.org/repo ubuntu-$RELEASE main"
     keyserver: hkp://p80.pool.sks-keyservers.net:80
     keyid: 58118E89F3A912897C070ADBF76221572C52609D
     filename: 'docker.list'
  packages:
   - docker-engine

I'll attach /run/docker.install.out and 'systemctl-status -l docker-service' and 'journal -xe' but I actually think we have to get docker run with more verbose output as I think its eating some useful error.