For anyone else out there trying to set up Apple Mail to check their Gmail account and getting an "Invalid credentials" error:

You may need to unlock CAPTCHA for your Gmail account:
https://www.google.com/accounts/UnlockCaptcha

Just go to that page, fill out your information and everything should work. I'm not sure if there are larger ramifications of doing this, but I suspect it's not much of an issue. Any ideas on the security implications? Reading around on Google Groups and the Apple Forums it also seems like this issue may also affect the iPhone as well. I hope this helps if you're having that issue.