AWS reporting InvalidInstanceID.NotFound when new instance is started:
"Error allocating node for step 'master': Status Code: 400, AWS Service: AmazonEC2, AWS Request ID: ecd3c270-6302-409b-8edc-a9b92489e856, AWS Error Code: InvalidInstanceID.NotFound, AWS Error Message: The instance ID 'i-0a5d92ed' does not exist"

In this situation the instance id does actually exist on AWS side, but during setup there was most likely some eventual consistency of the API validation. This is well possible accordingly to the page of AWS API documentation: http://docs.aws.amazon.com/AWSEC2/latest/UserGuide/query-api-troubleshooting.html

Checking the QuickBuild Application code it is visible that the following rules are not applied in there which means that the consistency is not guaranteed:
* Confirm the state of the resource before you run a command to modify it. Run the appropriate Describe command using an exponential backoff algorithm to ensure that you allow enough time for the previous command to propagate through the system. To do this, run the Describe command repeatedly, starting with a couple of seconds of wait time, and increasing gradually up to five minutes of wait time.
* Add wait time between subsequent commands, even if a Describe command returns an accurate response. Apply an exponential backoff algorithm starting with a couple of seconds of wait time, and increase gradually up to about five minutes of wait time.