unable to connect to AWS VPC RDS instance (mysql or postgres)

(I'm posting this question after the fact because of the time it took to find the root cause and solution. There's also a good chance other people will run into the same problem)

I have an RDS instance (in a VPC) that I'm trying to connect to from an application running on a classic EC2 instance, connected via ClassicLink. Security groups and DNS aren't an issue.

I am able to establish socket connections to the RDS instance, but cannot connect with CLI tools (psql, mysql, etc.) or DB GUI tools like toad or mysql workbench.

Direct socket connections with telnet or nc result in TCP connections in the "ESTABLISHED" state (output from netstat).

Connections from DB CLI, GUI tools, or applications result in timeouts and TCP connections that are stuck in the "SYN" state.

UPDATE: The root cause in my case was a problem with MTU size and EC2 ClassicLink. I've posted some general troubleshooting information below in an answer in case other people run into similar RDS connectivity issues.