Ever since Apple introduced the Internet Accounts way of setting up email on Apple Mail a few years ago I have been unable to setup my Google Apps account, I've tried looking for similar issues but just can't find a solution anywhere.
The first thing I do is select Google from the list in System Preferences > Internet Accounts. Then enter my username and password into the google login form. Then enter my 2-step Verification code and accept the permissions request.
Then OS X asks what apps I would like to use with my account. I leave all ticked. Then almost immediately I get this error:
Then I get this the same error for my Notes which also uses IMAP.
I have tried multiple computers and have no issue with iOS setup. Just OS X. I've setup other Google Apps accounts with the exact same DNS settings and don't have this issue with them.
Best Answer
It appears that you may be in the United Kingdom, and it appears that there is an issue with how you need to set up email accounts within Apple Mail for .co.uk domains.
Apple provides this web app to allow you to enter your email account and returns a page such as this:
As I am trying this from the States, it is likely that the web app senses my location so it will likely be different settings for you. I am not sure if this will give you something different than what you have already entered, however there may be some weird Server Port that you need to set in order for Apple Mail to work with a UK based Mac and your @unknowndomain.co.uk Google Apps account.
You will need to go under Mail>Preferences>Accounts, then select the gmail account and click on the Advanced tab to enter in the port that the web app returns.
Apple also has Mail Connection Doctor; which can help to diagnose if you still have no joy.
It may also be that you have not enabled IMAP on your Google Apps account. Follow these instructions on how you do that in gmail. This support page for Google Apps administrators may also have additional information that you need to follow.
It appears that you do not want to go the Application Specific Password route for a specific reason. I still think that the problem is likely something to do with the ports that you need to enter or enabling IMAP on your Google Apps account.
I hope you find an answer.
Update
Maybe this will help, or at least explain why it may not be working for you?...
Autodiscover for Google Apps