This is the entire lead-up:
2012-06-26 04:08:42,305: juju.ec2@DEBUG: Creating juju machine security group juju-devstack-7
2012-06-26 04:08:42,531: juju.ec2@DEBUG: Launching with machine spec MachineSpec(instance_type='m1.small', image_id='ami-00000004')
2012-06-26 04:08:43,289: juju.state.expose@DEBUG: Assigned units for machine 7: old=None, new=set(['elasticsearch/0'])
2012-06-26 04:08:43,421: juju.state.expose@INFO: No provisioned machine for machine 7
2012-06-26 04:09:13,687: juju.agents.provision@INFO: Starting machine id:7 ...
2012-06-26 04:09:13,707: juju.ec2@WARNING: ssl-hostname-verification is disabled for this environment
2012-06-26 04:09:13,707: juju.ec2@WARNING: EC2 API calls not using secure transport
2012-06-26 04:09:13,708: juju.ec2@WARNING: S3 API calls not using secure transport
2012-06-26 04:09:13,708: juju.ec2@WARNING: Ubuntu Cloud Image lookups encrypted but not authenticated
2012-06-26 04:09:14,063: juju.ec2@DEBUG: Cannot delete security group juju-devstack-7: Error Message: An unknown error has occurred. Please try your request again.
2012-06-26 04:09:14,065: juju.agents.provision@ERROR: Cannot process machine 7
Traceback (most recent call last):
  File "/usr/lib/python2.7/dist-packages/juju/agents/provision.py", line 187, in process_machines
    machine_state_id, provider_machines)
  File "/usr/lib/python2.7/dist-packages/twisted/internet/defer.py", line 1037, in _inlineCallbacks
    result = result.throwExceptionIntoGenerator(g)
  File "/usr/lib/python2.7/dist-packages/twisted/python/failure.py", line 382, in throwExceptionIntoGenerator
    return g.throw(self.type, self.value, self.tb)
  File "/usr/lib/python2.7/dist-packages/juju/agents/provision.py", line 228, in process_machine
    {"machine-id": machine_state.id, "constraints": constraints})
  File "/usr/lib/python2.7/dist-packages/twisted/internet/defer.py", line 1037, in _inlineCallbacks
    result = result.throwExceptionIntoGenerator(g)
  File "/usr/lib/python2.7/dist-packages/twisted/python/failure.py", line 382, in throwExceptionIntoGenerator
    return g.throw(self.type, self.value, self.tb)
  File "/usr/lib/python2.7/dist-packages/juju/providers/common/launch.py", line 64, in run
    machines = yield self.start_machine(machine_id, zookeepers)
  File "/usr/lib/python2.7/dist-packages/twisted/internet/defer.py", line 1037, in _inlineCallbacks
    result = result.throwExceptionIntoGenerator(g)
  File "/usr/lib/python2.7/dist-packages/twisted/python/failure.py", line 382, in throwExceptionIntoGenerator
    return g.throw(self.type, self.value, self.tb)
  File "/usr/lib/python2.7/dist-packages/juju/providers/ec2/launch.py", line 42, in start_machine
    security_groups = yield self._ensure_groups(machine_id)
  File "/usr/lib/python2.7/dist-packages/twisted/internet/defer.py", line 1037, in _inlineCallbacks
    result = result.throwExceptionIntoGenerator(g)
  File "/usr/lib/python2.7/dist-packages/twisted/python/failure.py", line 382, in throwExceptionIntoGenerator
    return g.throw(self.type, self.value, self.tb)
  File "/usr/lib/python2.7/dist-packages/juju/providers/ec2/launch.py", line 114, in _ensure_groups
    % (juju_machine_group, e.get_error_messages()))
ProviderInteractionError: Unexpected EC2Error deleting security group juju-devstack-7: An unknown error has occurred. Please try your request again.


So to me, it looks like calling terminateInstances is needed in there.