In my case it was not a plugin issue at all or a settings issue.
This is for everyone that hosts their sites on Bluehost, which is where my client's site was hosted.
Up until this point my client was using domain email so everything was working like it was intended. did not need the smtp plugin.
He then switched to Google Apps and used gmail for his mx exchange to take advantage of all the resources that integrate with it.
We were still using his domain email address but it was not ending at Bluehost but rather redirected to Gmail so Bluehost Blacklisted his site.
After further research into this, earlier this year Bluehost changed their Spam Settings and automatically blacklist all email that is not resolving to their email servers. So no email going through to gmail.
Once I found this out I got on live chat with Bluehost and sure enough it was blacklisted. Once they whitelisted my client's domain the smtp plugin could connect again and all was happy again.
It took 6 sessions on live chat (30 minute wait time every time) with them to finally convince them to look for this. They kept saying all your settings are correct there is no reason for this it just needs to propagate.
The first time I got on chat before I found out about the automatic blacklist I made the "is this domain blacklisted" suggestion to their live chat support. But they told me it wasn't the issue. Many wasted hours but it works.