Two-Step Authentication, iPhone Mail.app, and SMTP I have setup Two Step Verification for my Google account and all is well getting into email from a browser, or from the Safari browser on my phone.

However, I cannot get Mail.app to work. It just tells me the password is wrong. I am using an application specific password generated from the account access page in Google, tried two, still no go.

How can I get the Mail.app to actually work with this?
Open up the keychain application and locate the password that it has stored for your gmail account.  Now delete it.

Then retry the process you have, ensure you put in your application specific password, and then ensure you press the checkbox that says to save password to keychain.

Further instructions and Mail.app specific screenshots here.

I believe that mail.app is using an older stored email and this is preventing access.  I am assuming of course that mail.app was working perfectly for you before you started using two step authentication.