I'm in trouble on setting up a MySQL RDS.
From my EC2 instance I can connect fine, but from my laptop I get error 2003 (timeout).
Should I configure something on my VPC or Internet Gateway?
As your security groups are wide open, my guess is that your LAN is blocking outbound traffic on port 3306. Infact, looking at this support page ( http://docs.aws.amazon.com/AmazonRDS/latest/UserGuide/USER_ConnectToInstance.html ) firewall issues are listed as number 2 in common reasons for being unable to connect.
This question may help you out: MySql networking issue. May be worth taking a look at your local firewall settings. You mention you are on a laptop so my guess is your current network is classed as a public network and your outbound ports are being blocked (as mentioned in the question Ive linked).
If that gets you nowhere, its worth telnetting to your RDS instance on port 3306 and seeing what happens. This may well give you some more debug information which could help with the general Googling around of the issue.
As an aside, personally I wouldn't open up an RDS instance to the Internet directly. Its reasonably straight forward to setup an ssh tunnel to forward traffic to your RDS instance through an SSH server. Something like the stuff shown here: http://www.techrepublic.com/blog/linux-and-open-source/tips-and-tricks-to-help-you-do-more-with-openssh/
UPDATE: I've never used RDS with the 'publicly available' option (all our setups used ssh tunnelling to private RDS instances). Googling around, I came across quite a few queries in the AWS forums relating to access issues to public RDS instances. For example, https://forums.aws.amazon.com/thread.jspa?threadID=123483. May be worth trying the suggested fix of explicitly creating entries in the route table for the subnets that compose the RDS instance?