I got this error message today, and then found out that the default VPC was missing in the region where I wanted to start the instances. Going to the AWS Console and choosing "Create default VPC" fixed it for me.