Generally, ideas for games involving time travel fall flat on their face. Mostly because they lack the concepts we generally connect to the idea of time travel, ie. screwing with peoples lives and then undoing it by going back in time and killing yourself before you do so. Here's my idea which I hope will include this and other concepts.
The premise: The year is 9001. The world is your stereotypical techno-punk society. You are a member of a team which safeguards history from temporal doomsday scenarios. (I doubt any of you have played it but similar to the Journeyman games). The game would probably have different arcs, maybe even come in episodes. Each different episode would give you access to a certain range of time, maybe a span of days, maybe a span of years, maybe months, and each episode might take place in a different location in history.
Gameplay: The world of the game would be sandbox like, probably the size of Oblivion, or larger (especially if there were vehicles). The combat would vary depending on the time period and situation you are dropped into, as the weapons you would use would be local to that time period. In other words, arrows and blades for the middle ages, muskets and sabers for later romantic periods, guns for WWI and WWII (Yes, there would be SHOOTAN), and possibly beam sabers and laser guns if there were futuristic time periods. There would be quests all around, but not the kind of "fech 4 anmial skns 4 me plox" type of quests. These quests would be relayed to you through your temporal interface. They would be things such as "That guy's about to kill this historically significant person! STOP HIM!" or "You need to climb the tree and drop an apple on Newton since he chose to sit until the damn maple tree instead." There would be main temporal goals as well that you would have to complete across the span of history you are present in which would serve as the main quest.
Time jump:You would be able to time jump to almost any point in the time period provided no one local to the time space location was watching you. This would probably not break most quests, because of the next feature.
Paradox Immunity: Your time equipment would be specially equipped to withstand the temporal backlash that results as the history of your previous actions are altered. In other words, you could go back into the past and kill yourself without destroying history or yourself. The only consequence would be a "Temporal Shockwave Detected" warning just before the whole of the temporal space time dimension your previously occupied exploded in a blaze of fancy eye candy effects leaving you behind and ready to jump into another point in history, having undone any actions you did between the time you were killed and the time you killed yourself. This would allow you to undo any accidental damage to history, as well as any screwing around with major historical figures.
Problems and Solutions: Of course this creating a history of your actions is mildly problematic as what if you are too lazy to go kill yourself (even if there's an indicator showing where you were at all points in time). For those, there would be the option to just refresh the temporal dimension to the way it was before you started. The problem with this would be having to do the WHOLE main quest over again. For this reason, the main time consuming element of the game would be the uncovering of the dates/persons/locations of main quest critical events. Once you have uncovered these critical pieces of information, fixing these events would be very easy. Compare it to Myst's ability to be ended in 5 minutes if you know what to do. You would keep track of important data in your ChronoLog of course.
Conclusions: Modding would probably be a key feature I'd also want to include, especially if it would be much in the spirit of The Elder Scrolls, as I'd want it to be. So expect your catgirl player characters within a few weeks of the time the Japanese modding community gets a hold of it..