Long connection times from PHP to MySQL on EC2
How well does it work if you eliminate PHP from the equation? Use the CLI mysql client to connect to the server. Try it from both the db server itself and from the app server:
time mysql -h localhost -D dbname -u username -ppassword -e ''
Check your DNS servers, I think mysql might be trying to resolve the reverse DNS of the connecting host. Also make sure /etc/hosts is sane and has "127.0.0.1 localhost"