I'm experiencing a strange issue with a fabric script I'm using to bootstrap a server on EC2.

I launch a stock Ubuntu 12.04 AMI, wait for it to start, then proceed with:

with settings(host_string="ubuntu@%s" % i.dns_name, 
              connection_attempts=30):
    sudo('apt-get -qy update')
    sudo('apt-get -qy install --no-install-recommends mdadm') # don't install postfix
    #etc...

The apt-get update appears to run fine and gives no errors, however (2/3 of the time or so) installing mdadm throws a "no installation candidate" error.

When I ssh into the server and run apt-get install mdadm I get the same error. Running apt-get update by hand, then the package installs fine.

Any ideas on what might be happening, or ideas for debugging?