私もﾊﾟｽﾜｰﾄﾞ再発行したことは当然ありますが､PC,iPod touchでも同様との現象ですので｢一発目から弾かれる｣というのは経験したことないです｡
入力ﾐｽか何かだと思います｡
それ以外だと､直接 googleに問い合わせてみては如何でしょうか｡
http://www.google.com/intl/ja_jp/contact/

ﾊﾟｽﾜｰﾄﾞの再発行で送られてくるﾒｰﾙを読んで､そこに記載されているURLに飛んで本人確認がちゃんと取れないと入れない仕組み｡仮認証止まりなんじゃ？

ごめんなさい｡@のあとがGmail.co.jpになってました｡
gmail.comにしたので解決しました｡
お騒がせしてすみませんでした｡