Check this out first:
http://email.about.com/od/accessinggmail/f/Gmail_SMTP_Settings.htm
Just verify it's not a connection setting first. Maybe gmail changed something; Who knows.
Go to ACP > Stats & Logs > Logs > Email Error Logs
If it's empty, great. If not, and it's full of recent errors, it's your connection settings. But if it's clean then it's a blacklist issue.
I just want you to troubleshoot that possibility before you begin dealing with blacklists. They are time consuming to work around and sometimes if the issue isn't properly fixed, you will just be put back on there.