MySQL "Access denied for user" after moving to new server
Seems this is not a Craft issue at all, but an issue with MySQL connections over PDO. Not sure of the precise environmental conditions that cause this, but I was experiencing the issue on both an AWS EC2 Ubuntu server as well as a MySQL RDS instance.

I discovered the solution here: https://stackoverflow.com/questions/38809418/unable-to-connect-to-aws-rds-through-pdo

In short, the ! in my password was causing the problem. After replacing it with a ., the issue is resolved.

Thanks Amazon...