Got a reply from an AWS staffer that wasn't helpful in solving the problem.
Are you connecting to the SMTP endpoint in the same AWS Region where you verified the email address? When you verify an email address or domain, the verification only applies to the Region that you verified it in.
For example, if you verified an email address in the US East (N. Virginia) Region, then you'd receive the "Email address not verified" error if you tried to send an email by connecting to the email-smtp.us-west-2.amazonaws.com endpoint (in this case, you'd have to connect to email-smtp.us-east-1.amazonaws.com instead).
I hope this information helps. Let me know if I can provide any additional information.
Added additional information to the Forum post. Also tested the email address this morning and got the same SMTP error.