Two-Step Authentication, iPhone Mail.app, and SMTP
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.