I just tried, I got the "rejected by the server" message using Apple's Mail the first time, but I just resent and chose the same server, smtp.gmail.com, and they go through now.

I've noticed over the last couple of days or so from Mail gmail has rejected my password two or three times, but I just click cancel and the next time it checks for mail it is okay. May be some bad voodoo going on with gmail.