Morgon77: The many-worlds hypothesis doesn't actually resolve this issue. The world in which the time-traveler shoots himself is still the same world in which the time-traveler exists, and hence can't have shot himself.
The essential problem is actually that of the cause and effect model of reality. This model holds that: (a) no event is without a cause and (b) no effect can cause its own cause (which is really just another way of stating (a)). The time-travel paradox can be resolved by supposing that, at the moment time-travel is developed, the universe bifurcates into one set of universes where time travel exists, one set where it doesn't, and in the set with time travel, there can be effects without causes; for instance, a time traveler can go back in time, kill himself, but continue to exist. He comes into existence at the moment of his appearance, his future self no longer exists.
Of course, in a universe where time travel is possible, all sorts of other laws of physics would have to go, such as conservation of mass; by traveling forward and backward in time, mass (such as gold bars) can be multiplied.