Always an interesting question. If we define time travel to mean departure from a certain place and time followed (from the traveller's point of view) by arrival at the same place at an earlier (from the sedentary observer's point of view) time. Time travel paradoxes arise from the fact that departure occurs after arrival according to one observer and before arrival according to another. In the terminology of special relativity time travel implies that the timelike ordering of events is not invariant. This violates our intuitive notions of causality. However, intuition is not an infallible guide, so we must be careful. Is time travel really impossible, or is it merely another phenomenon where "impossible" means "nature is weirder than we think?"
It is sometimes argued that time travel violates conservation laws. For example, sending mass back in time increases the amount of energy that exists at that time. Doesn't this violate conservation of energy? This argument uses the concept of a global conservation law, whereas relativistically invariant formulations of the equations of physics only imply local conservation. A local conservation law tells us that the amount of stuff inside a small volume changes only when stuff flows in or out through the surface. A global conservation law is derived from this by integrating over all space and assuming that there is no flow in or out at infinity. If this integral cannot be performed, then global conservation does not follow. So, sending mass back in time might be all right, but it implies that something strange is happening. (Why shouldn't we be able to do the integral?)
The possibility of time travel in GR has been known at least since 1949 (by Kurt Godel). The GR spacetime found by Godel has what are now called "closed timelike curves" (CTCs). A CTC is a worldline that a particle or a person can follow which ends at the same spacetime point (the same position and time) as it started. A solution to GR which contains CTCs cannot have a spacelike embedding - space must have "holes" (as in donut holes, not holes punched in a sheet of paper). A would-be time traveller must go around or through the holes in a clever way.
The Godel solution is a curiosity, not useful for constructing a time machine. Two recent proposals, one by Morris, et al. [2] and one by Gott [3], have the possibility of actually leading to practical devices (if you believe this, I have a bridge to sell you). As with Godel, in these schemes nothing is locally strange; time travel results from the unusual topology of spacetime. The first uses a wormhole (the inner part of a black hole) which is held open and manipulated by electromagnetic forces. The second uses the conical geometry generated by an infinitely long string of mass. If two strings pass by each other, a clever person can go into the past by travelling a figure-eight path around the strings. In this scenario, if the string has non-zero diameter and finite mass density, there is a CTC without any unusual topology.
The possible existence of time machines remains an open question. None of the papers criticizing the two proposals are willing to categorically rule out the possibility. Nevertheless, the notion of time machines seems to carry with it a serious set of problems...