I know others have gotten this to work, so there must be something I'm missing. First off, I have POP activated on my Gmail account for all mail. Now, the phone settings:

Your name: <my name>
E-mail address: <myemail>@gmail.com

User name: <myemail>@gmail.com
Password: <mypassword> (the one I use to log in on the web)
Domain: <blank>
Save password: <checked>

Server Type: POP3
Account name: Gmail
Network: The Internet

Incoming Server: pop.gmail.com (also tried pop.gmail.com:995)
Require SSL: <checked>
Outgoing server: smtp.gmail.com (also tried smtp.gmail.com:465)
Outgoing server requires authentication: <checked>

In Outgoing server settings:
Use different password: <not checked>
Use SSL: <checked>

Download the following: 3 days worth, first 1000 bytes

Never connect automatically (I'll probalby change this, but I wanna get it working first)

That's it ... how does that compare to your settings, if you've gotten it to work? This is driving me nuts!