This is an issue that I run across every time I modify my two-step verification settings in Gmail or set up a new phone. I've asked this question to Google enough times. Now I think I'm qualified to ask it to myself.
If you've set up Gmail as your default Mail app account and you use two-step verification, then Mail won't work if you haven't properly set up your device (and you might not even know it's not working if you're using the Gmail app as your main mail app until you try to share via email something in another app and realize it never gets sent).
There doesn't seem to be a simple user-friendly answer to this problem out there, so after running into this issue and solving it yet again, I figured I'd write out instructions for others to follow.