Can't send email from BB Passport for account associated with HostGator, why?

I have multiple email accounts setup in my BB Passport.
1 Hotmail, 1 Outlook, 1 Gmail and 2 from our website that is hosted with HostGator.
All of them were working fine for years. Recently, around March 9, no one has been receiving my replies or new emails sent from HostGator account. I receive all emails just fine, but I can't send anything. All other accounts work fine. I can sent emails from Hostgator account from my computer, using outlook 2010 and from my wife Nexus 4 and 5. My partner as a Z10 and is experiencing same issue with his email with same domain name. Funny thing is that if I send him an email from my HostGator account to his, he receives it fine. Looks like it won't send email to another provider.
I have contacted customer support from Blackberry and HostGator and both are puzzled. I have tried deleting the account from phone and email provider, changed ports on send server. I also "factory reset" my phone.
If anyone has ever had that problem, any help would be appreciated.

Edit: I have been testing for over a week now with configurations. Found this to work sending email back and forth to my Gmail account from my Telus phone
Essentially what I have done is change my outgoing smtp from mail.myserver.com to smtp.telus.net and removed my email address. More testing tomorrow.
http://business.telus.com/en/busines...n-any-computer

I had the exact same problem, I thought it was because I changed from my Z to a Q. Now I guess it's just a coincidence.
I have switched back and forth a few times, still no resolution. I sent a support ticket to host gator with no answer yet.
This is so frustrating as I try to run a business with my phone.

Sent while driving from my Crackberry.