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.
I see, you didn't mention that, you only mentioned gmail at first. Karnac didn't know.
My first thought is since it's a PC reboot to clear DNS.
What smtp server were you using? Maybe it's just having temporary problems. Or it could still be a temporary problem with gmail's pop servers rejecting incoming email, they did reject my password recently like I mentioned.