Google Authenticatorを使っていたのですが、携帯を買い替えた際に設定が消えてしまったので再度設定をしなおしたところ、何か間違えていたらしく、ログインできなくなってしまいました。
このような場合、リカバリコードを保存してあれば代わりに使うことができますが、私は紛失していました。
同様の対処はヒャッハー!Githubから締め出しくらったぜぇ!に詳しいのですが、こうなると元のアカウントを復帰させることはできません。
Warning: For security reasons, GitHub Support cannot restore access to accounts with two-factor authentication enabled if you lose your phone and don't have access to your recovery codes.
About Two-Factor Authenticationにもあるように、githubではアクセス権を復旧しないと明言されています。
取れる手は別名アカウントの再取得のみです。今度はリカバリコードもきちんと保存しました。
1点困ったことが、すでにgithubのアカウントに関連付けられているメールアドレスでは新規アカウントの登録ができません。
これは問い合わせページから英語で問い合わせを送る必要があります。私の場合、問い合わせに使ったメールを旧アカウントから削除してもらい、新規アカウントを作ることができました。