Just seems rather coincidental that this all started when HostGator updated their servers. But maybe it is a GoDaddy problem. I guess I'll encourage my clients to use gmail accounts in the future. It's really annoying that HostGator blames GoDaddy and GoDaddy blames HostGator rather than trying to figure out what's wrong.
Thanks for the help. At least when they tell me it's my code, I can tell them NOT SO!