If you haven't seen it yet, WebmasterWorld has a thread named My email automatically rejected, which discusses how some ISPs are blocking emails from gmail addresses.
The emails are being blocked because of all the privacy issues surrounding the GMail service.
One of my favorite quotes in this thread is:
And please don't make the "it's the same as running a spam filter" argument. Filtering spam doesn't put an ad for a competitor on content I created.
However, I am of the type that only uses Webmail for junk mail. My real email is owned, powered and hosted by myself. I have junk accounts with Yahoo, hotmail and others - Yahoo being my primary. So in my mind, its no big deal at all to have these emails read by Google's Ad servers. However, there are thousands of people who use free, Web based email services for their real email accounts. I can see the problems with that.
ISPs have the power to block Gmail, so some are. Join the discussion at WebmasterWorld.