Today Major Nelson stated on his blog that the process has begun to make previously used or unavailable gamertags available again. The process will take some time; the gamertag you want may not be available right away. If there is a gamertag that you’ve wanted to use but was previously taken, you may now be change yours to the one you want. Just select “change gamertag” in the My Xbox channel on Xbox Live. Dead gamertags shall live once again!