Since installing Lion and running two machines in parallel - Lion and Snow Leopard I was getting errors connecting to gmail/google apps IMAP - it kept throwing an incorrect password error.

Finally found this FAQ:

https://mail.google.com/support/bin/static.py?page=known_issues.cs&ki_topic=14973&issue=1210103&bucket=14977&hl=en

If you're having this issue - might be worth hitting the FAQ while logged in and hitting the Report button.