An Elastic BeanStalk launched in a VPC with a private subnet requires a NAT. Each instance needs to be able to talk to the Internet in order to answer the waitcondition. Connectivity can be provide through a NAT instance but there does have to be access to the internet.
The following show a VPC configuration with a private VPC. It is the connectivity to the Elastic Beanstalk end point that is needed. As you can see it is outside the VPC.
You can find more detailed instructions for creating and configuring a NAT instance here: