I have no problem with time travel in and of itself, but it has to be consistent with its own rules. If a supposedly serious time travel story has worse internal consistence than Bill and Ted’s Excellent Adventure (a comedy), then I’m not interested. 
For an example: The Butterfly Effect is a story about a man who can travel back to certain moments in his childhood and change his actions then, thus causing a “butterfly effect” meaning that even the smallest change will create a completely different present. The rules are obvious, and made very clear. Except that: one trip back changes nothing (instead being responsible for something earlier in the film, which is closer to Bill and Ted’s rules), one trip back only gives him stigmata (and changes absolutely nothing else), and the effects of changing earlier events in his childhood change nothing in his later childhood (despite the fact that the butterfly effect means that they really should…) At least Deja Vu (which is also bad) admits that it’s breaking its own rules… 
I would amend that to “If your story has time travel, it should become about time travel.” It can’t just be used as a get-out-of-jail-free card, but if it’s the point of the story (and is done well), then I’ve got no problem with that. 