Comment 17 for bug 1271144

I applied this patch and it worked:
=== modified file 'provider/maas/environ.go'
--- provider/maas/environ.go revid:tarmac-20140314141156-nsn5oeamfi31t1ct
+++ provider/maas/environ.go 2014-03-19 16:54:28 +0000
@@ -266,7 +266,13 @@
  userdata, err := environs.ComposeUserData(
   args.MachineConfig,
   runCmd,
- "apt-get install bridge-utils",
+ "cat /etc/apt/sources.list",
+ runCmd,
+ "cat /etc/apt/sources.list.d/*.list",
+ runCmd,
+ "apt-get update",
+ runCmd,
+ "apt-get install -y bridge-utils",
   createBridgeNetwork(),
   linkBridgeInInterfaces(),
   "service networking restart",

(of course, the cat's are just for extra debugging)

cloud-init-log:
Cloud-init v. 0.7 running 'modules:config' at Wed, 19 Mar 2014 17:34:46 +0000. Up 35.09 seconds.
Generating locales...
  en_US.UTF-8... done
Generation complete.
Cloud-init v. 0.7 running 'modules:final' at Wed, 19 Mar 2014 17:34:50 +0000. Up 38.23 seconds.
deb http://us.archive.ubuntu.com//ubuntu precise main restricted universe multiverse
deb http://us.archive.ubuntu.com//ubuntu precise-updates main restricted universe multiverse
deb http://us.archive.ubuntu.com//ubuntu precise-security main restricted universe multiverse
#deb http://ppa.launchpad.net/maas-maintainers/maas-ephemeral-images/ubuntu precise main
Get:1 http://us.archive.ubuntu.com precise Release.gpg [198 B]
(...)
Unpacking bridge-utils (from .../bridge-utils_1.5-2ubuntu7_amd64.deb) ...
Processing triggers for man-db ...
Setting up bridge-utils (1.5-2ubuntu7) ...
stop: Unknown instance:
networking stop/waiting