If one availability zone is down, there will be suddenly be ton of extra people trying to start new instances in the other availability zones. Could there just be a shortage of available instances in the other availability zones? Perhaps Amazon don't keep enough spare capacity for this eventuality (nor would I expect them to)?