Still affects juju (2.0.2) with lxc (2.0.10) and maas (2.2.2-6099-g8751f91) on latest Xenial (16.04.3 LTS). 

In my case, the 'maas' network is as follows (as documented and described in numerous HOWTO and training guides):  

<network connections='1'>
  <name>maas</name>
  <uuid>b97f7d0e-66e0-40b9-b6c9-274ead6f1c36</uuid>
  <bridge name='virbr1' stp='on' delay='0'/>
  <mac address='52:54:00:63:36:54'/>
  <domain name='maas'/>
  <ip address='192.168.100.1' netmask='255.255.255.0'>
  </ip>
</network>

Pods work, commission and deploy works, but bootstrapping juju on a cloud, does not.

Cloud config is: 

clouds:
   dev-maas:
      type: maas
      auth-types: [oauth1]
      endpoint: http://192.168.100.1/MAAS

Relevant debug output is: 

02:51:44 DEBUG juju.cloudconfig.instancecfg instancecfg.go:782 Setting numa ctl preference to false
Waiting for address
Attempting to connect to 192.168.100.4:22
02:51:44 DEBUG juju.provider.common bootstrap.go:396 connection attempt for 192.168.100.4 failed: Warning: Permanently added '192.168.100.4' (ECDSA) to the list of known hosts.
/var/lib/juju/nonce.txt does not exist
02:51:49 DEBUG juju.provider.common bootstrap.go:396 connection attempt for 192.168.100.4 failed: /var/lib/juju/nonce.txt does not exist
02:51:56 INFO  juju.cloudconfig userdatacfg_unix.go:346 Fetching agent: curl -sSfw 'tools from %{url_effective} downloaded: HTTP %{http_code}; time %{time_total}s; size %{size_download} bytes; speed %{speed_download} bytes/s ' --retry 10 -o $bin/tools.tar.gz <[https://streams.canonical.com/juju/tools/agent/2.0.2/juju-2.0.2-xenial-amd64.tgz]>
02:51:56 DEBUG juju.utils.ssh ssh.go:292 using OpenSSH ssh client
sudo: unable to resolve host kind-gator: Connection timed out
Logging to /var/log/cloud-init-output.log on the bootstrap machine
Running apt-get update
Running apt-get upgrade
Installing curl, cpu-checker, bridge-utils, cloud-utils, tmux
Fetching Juju agent version 2.0.2 for amd64

It will hang forever here, until I kill the kvm instance. 

The last chunk of lines in /var/log/cloud-init-output.log on the bootstrap node are: 

Unpacking cloud-utils (0.27-0ubuntu24) ...
Processing triggers for man-db (2.7.5-1) ...
Processing triggers for libc-bin (2.23-0ubuntu9) ...
Processing triggers for install-info (6.1.0.dfsg.1-5) ...
Setting up libiscsi2:amd64 (1.12.0-2) ...
Setting up distro-info (0.14build1) ...
Setting up genisoimage (9:1.1.11-3ubuntu1) ...
Setting up libaio1:amd64 (0.3.110-2) ...
Setting up libboost-iostreams1.58.0:amd64 (1.58.0+dfsg-5ubuntu3.1) ...
Setting up libboost-system1.58.0:amd64 (1.58.0+dfsg-5ubuntu3.1) ...
Setting up libboost-random1.58.0:amd64 (1.58.0+dfsg-5ubuntu3.1) ...
Setting up libboost-thread1.58.0:amd64 (1.58.0+dfsg-5ubuntu3.1) ...
Setting up libnspr4:amd64 (2:4.13.1-0ubuntu0.16.04.1) ...
Setting up sharutils (1:4.15.2-1) ...
Setting up libnss3-nssdb (2:3.28.4-0ubuntu0.16.04.2) ...
Setting up libnss3:amd64 (2:3.28.4-0ubuntu0.16.04.2) ...
Setting up librados2 (10.2.7-0ubuntu0.16.04.1) ...
Setting up librbd1 (10.2.7-0ubuntu0.16.04.1) ...
Setting up qemu-block-extra:amd64 (1:2.5+dfsg-5ubuntu10.15) ...
Setting up qemu-utils (1:2.5+dfsg-5ubuntu10.15) ...
Setting up cloud-image-utils (0.27-0ubuntu24) ...
Setting up cloud-utils (0.27-0ubuntu24) ...
Processing triggers for libc-bin (2.23-0ubuntu9) ...
Reading package lists...
Building dependency tree...
Reading state information...
tmux is already the newest version (2.1-3build1).
0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
Attempt 1 to download tools from https://streams.canonical.com/juju/tools/agent/2.0.2/juju-2.0.2-xenial-amd64.tgz...

That's it. It never completes, nor does it time out or give any other useful debug or other info I can use to further instrument this failure.