They do have to accept a connection from sendmail to work though it may be a different port and according to this Configuring Sendmail to relay through Gmail SMTP gmail upgrades to TLS. For the shared host check and see if they've made any changes to their SMTP.
Sorry for my late response.
If there is anyone else suffering from this same issue, using sendmail thru google did work for me. I guess now all I have to do now is configure sendmail to use one of my servers.
Thanks gregm for all your help!