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_to...
If you're having this issue - might be worth hitting the FAQ while logged in and hitting the Report button.