A couple of possible answers exist to the paradoxes proposed in relation to time travel:
1) The "Pastwatch" solution - used in Orson Scott Card's "Pastwatch: The Redemption of Christopher Columbus", this proposes that time travel effectively short-circuits the timeline, eliminating the timewise universe beyond that point. No paradox, since the person who has come back is not in that universe. Could conceivably imply that forward time travel is not possible, but not necessarily, since a new future history must necessarily come to exist.
2) Many-worlds - one version of this has already been discussed, the
Everett Interpretation.
2b) Another claims that the current moment is a pinch point, but that the future and past show many-worlds behaviour, with an ever-expanding set of possibilities the further away from the present you go. This relies on the collapse of the QWF, and is pretty much pseudo-science at best, but it's an interesting variation when applied wisely.
2c) Another variation is somewhat touched on by Charlie Stross in "Singularity Sky", in that he talks about how any universe that allows time travel is necessarily unstable, and so a far-future agency bans time travel. The outcome of this, in my mind, at least, is that a stable universe might allow time travel, but in any stable version of itself, the interesting time travel has already been done, and cannot be witnessed by members of the distant future or past, since they would have ridden out the temporary instability in an extra-dimensional equilibrium seeking sense. This basically boils down to the "there are rules against changing the past" idea, since you're starting in a stable version of the universe, so either you try later and fail or you succeed, but it's already part of history.