Success! Xbox Live is back up.

Xbox Live gamertag recovery has finally worked for me. ;) Your mileage may vary.