The LoK series has a messed up view of time travel, and confused me way too much.
The way I see Time Traveler's immunity working is like this:
A person in a 1000ad, in Timeline A. This person (Person A) then Time Travels to 600ad, in Timeline A. Now, lets say that someone else (in what would now be Timeline B, due to history nessisarily being changed by Person A's mere presence in 600ad) in Timeline B then Time Travels to a previous date, like 400ad, and then blows up the planet. Since Person A would have Time Traveled previous to Person B, TTI grants him the fate of appearing in space, and having his lungs explode. Now, if Person B had Time Traveled before Person A, Person A would not have had TTI, and therefore would have not existed to time travel.