Since RDS requires you to have two availability zones when deploying in a VPC, you need to make sure that beanstalk is able to get to both of them via Network ACLs as well as the permissions for the instance based security groups.
Only your ELB and your NAT instance/NAT gateway need to be public subnets, everything else should be in private subnets.
Security groups are stateful and network groups are stateless so while you only need to allow inbound rules for the security groups, you need to allow BOTH inbound and outbound ports from your beanstalk subnet to both RDS subnets using Network ACLs. See Security in Your VPC.
Here is a sample eb create to create the beanstalk environment (replace square bracketed strings):
eb create [BEANSTALK_ENVIRONMENT] --instance_type m3.medium --branch_default --cname [BEANSTALK_CNAME] --database --database.engine postgres --database.version [x] --database.size 100 --database.instance db.m4.large --database.password xxxxxxxxx --database.username ebroot --instance_profile [BEANSTALK_EC2_IAM_PROFILE] --keyname [SSH_KEY_NAME] --platform "64bit Amazon Linux 2015.03 v1.3.0 running Ruby 2.2" --region us-east-1 --tags tag1=value1,tag2=value2 --tier webserver --verbose --sample --vpc.id [vpc-xxxxxx] --vpc.dbsubnets [subnet-db000001,subnet-db000002] --vpc.ec2subnets [subnet-ec200001] --vpc.elbsubnets [subnet-elb00001] --vpc.elbpublic --vpc.securitygroups [sg-00000001] --sample --timeout 3600
subnet-db000001 NETWORK ACL RULES:
Inbound: Port Range: 5432, Source [subnet-ec200001 (as ip range)], Allow
Outbound: Port Range: 5432, Source [subnet-ec200001 (as ip range)], Allow
subnet-db000002 NETWORK ACL RULES:
Inbound: Port Range: 5432, Source [subnet-ec200001 (as ip range)], Allow
Outbound: Port Range: 5432, Source [subnet-ec200001 (as ip range)], Allow
subnet-ec200001 NETWORK ACL RULES:
Inbound: Port Range: 5432, Source [subnet-db000001 (as ip range)], Allow
Inbound: Port Range: 5432, Source [subnet-db000002 (as ip range)], Allow
Outbound: Port Range: 5432, Source [subnet-db000001 (as ip range)], Allow
Outbound: Port Range: 5432, Source [subnet-db000002 (as ip range)], Allow
subnet-elb00001 NETWORK ACL RULES:
Inbound: Port Range: 80, Source 0.0.0.0/0, Allow
Inbound: Port Range: 443, Source 0.0.0.0/0, Allow
Outbound: Port Range: 80, Source 0.0.0.0/0, Allow
Outbound: Port Range: 443, Source 0.0.0.0/0, Allow
An additional note about Network ACLs -- many services don't respond on the original port but use an ephemeral port. So you may have to add the following to the inbound AND outbound network ACLs for subnets with EC2 instances:
Outbound: Port Range: 1024-65535, Source 0.0.0.0/0, Allow
Outbound: Port Range: 1024-65535, Source 0.0.0.0/0, Allow
There are also several useful scenarios in Recommended Network ACL Rules for Your VPC.
I hope this helps.
Best Answer
Do you have your RDS instance in a VPC? Are you sure that your RDS instance has the "Publicly Accessible" setting set to "Yes"?
If you want to be able to access your RDS instance from outside your VPC, you need to switch that option to "Yes".