We had a Google Apps account which we needed to use IMAP to connect in order to run a mailbox synchronisation using imapsync, but the credentials were being returned as invalid. We could log into the very same account on the web browser, but IMAP settings both at command line and in Thunderbird were coming back as invalid.
After much password checking, username checking, server hostname checking and everything else checking, we came to the conclusion there must be something else going on here. True to form, there was! We received an email in the mailbox we were trying to connect to, informing us that Google had prevented access because we were using a 'less secure application' - in our case connecting via command line or Thunderbird.
We uncovered the problem buried in a Google Product Forums post - https://productforums.google.com/d/msg/gmail/3Qk19hGgJeE/t8S0z4WNcsIJ - which suggests some reasons why your credentials might be flagged or you might not be able to log in via IMAP using these tools.
The process to remove this restriction was pretty simple - just head on over to https://www.google.com/settings/security/lesssecureapps and enable access for less secure apps - you can always re-enable it in the future.
As soon as we enabled this option, we were able to connect via IMAP and synchronise the mail.
Hopefully if you find yourself in this situation it will be a quicker fix! There are other suggestions in the post above if this doesn't fix it - such as a captcha being required or needing to adjust other settings. Two factor authentication can also cause problems if you have it enabled.