for me it came down to a rogue smtp server. in my case, my desktop machine uses the gmail smtp servers to sent outgoing mail from my comcast account because comcast's has always been flaky for me. when the phone synced, it brought over all of those settings/servers. not sure why, but, re-entering the smtp password in the smtp server for the comcast account--on the phone-- fixed the issue with gmail checking even though gmail had its own smtp server with the correct password.
as an aside, i don't think i'd tried sending mail from the comcast account from the phone, as gmail is set up as my default account. had i done so, i might have been able to troubleshoot this faster.
hope that's clear as mud. good luck.