I spent a fair while pondering this well-written article which explains the issue quite clearly (note how long the discussion following it goes on for!) and came to an interesting conclusion.
The article does leave open one huge loophole for sci-fi: if there was a universal reference frame by which ALL instantaneous teleportation occurred then this doesn't contradict Relativity or lead to causal paradoxes.
In brief, if all teleportation is relative to a universal reference frame, based upon Cosmic Microwave Backround radiation, relative to which all galaxies are moving well sub-light speed, and assuming all space travel is all well sub-light speed or via teleportation relative to the CMB, then there is no paradox and any time travel is only illusional and so slight as to be effectively ignorable :-)
My explanation is as follows:
Because (1) all motion is relative, and (2) the speed of light is constant, then perception of spacetime varies amongst observers with different velocities. The simplest consequence is that someone passing you at near the speed of light will perceive distances in the direction of their travel as being contracted. They think your spaceship looks squashed, but likewise you do theirs.
One consequence of your changed perception of distance is that it changes your concept of what events occur "simultaneously".
Let's assume there's a hoop 4 light years away, stationary relative to you, and you see a basketball going through that hoop. As it is 4 light years distant to you then you consider the goal to have occurred 4 years ago. But if someone passes you at high (relative) velocity at the moment you see the goal then they see it also but then due to length contraction they may consider the event to have occurred 3 light years away, and thus consider it to have occurred 3 years ago.
Note that the ball and the hoop may be moving at wildly differing velocities, and you may disagree on the velocity of the ball and hoop, the location and timing of the event, but you both agree that the ball went through the hoop (the event itself has no velocity, it is a single point on the Minkowski diagram).
Now, assume that instantaneous travel is possible and you go to somewhere else at a point in time there according to your perception of when "now" there is (based upon your own velocity). If your fellow observer teleports to the hoop and back, while you wait for a year before teleporting to the hoop and back, you'll find you both arrive at the hoop at the same moment.
This can create a causal paradox, thus a contradiction and hence one of the assumptions is false.
It is generally taken that the assumption that you can teleport is false, whereas in fact it is the assumption everyone teleports according their own perception which has been shown to be false.
This is a loophole (useful for sci-fi!) - if there was a universal reference frame (heretic!) by which all teleportation took place then no causal paradox occurs. Anyone currently at your location teleporting to the hoop would arrive there together, but you wouldn't all agree on when it was you arrived there. You might teleport 1 year into the past when you went to the hoop, and then return 1 year into the future on the way back, or vice-versa. You could (apparently) teleport up to 4 years in the past or the future (!!!) but this
would (effectively) be only a matter of perception as you wouldn't be time travelling with respect to the universal frame.
There is debate amongst physicists on the net about a universal reference frame, based upon Cosmic Microwave Backround radiation, suggesting that the earth isn't moving very quickly with respect to it, and
presumably nowhere near fast enough for any relativistic effects. Thus so long as space travel was all well sub-light speed or via teleportation relative to the CMB, then not only would the time travel be only illusional it would be so slight as to be effectively ignorable.
Obviously someone else spotted this before me, googling I found e.g. this.