The subnet you are trying to connect to must be in the same availability zone as the instance. When you go to create a VPC, you usually create it with one subnet. Click "edit public subnet" and then select an availability zone. For example I see us-east-1a, us-east-1c, and us-east-1d. By default it is "no preference", which I believe means it will choose one for you.
Alternatively you can add a new subnet to your VPC. You can set an availability zone for a subnet in the same manner as above.
Just to be clear - us-east-1c and us-east-1b are distinctly different availability zones.
Also, see the VPC FAQ
Q. Can I attach a network interface in one AZ to an instance in another AZ?
Network interfaces can only be attached to instances residing in the same AZ.
Q. Can I attach a network interface in one VPC to an instance in another VPC?
Network interfaces can only be attached to instances in the same VPC as the interface.