Deberías usar la búsqueda, es muy útil, y te aseguro que la pregunta ha sido respondida en múltiples ocasiones.
Para recuperar el gamertag, enciende la consola con tu disco duro nuevo, y una vez dentro del dashboard, en ''seleccionar/cambiar perfil'' usa la última opción: Recuperar gamertag. Mediante un proceso paso a paso donde te pedirán tu cuenta passport/live y tu contraseña, podrás volver a recuperar tu gamertag, con tus logros y gamerscore (No así las partidas guardadas)