Depends on how much of the story's structure, character motivations, etc, are changed by adding or removing bits. If TOS-R and TNG-R were remastered, but with any new effects used only to enhance the original without altering the live-action content of the story... the bulk of the episodes are just the same. A few new asteroids thrown in one episode doesn't make one story turned into another, see "The Doomsday Machine" and "Booby Trap" as two examples. Nor does adding a new Romulan ship in the background to complement the new Klingon design that they are also using due to presumably an alliance or stolen technology ("The Enterprise Incident"). Had season 3 more budget to play with, you can bet they'd have made a new Romulan model or found the old one or whatever.
Now, adding in deleted scenes and/or deleting others? That can and does change either context within a story, if not the story itself. Usually, scenes are cut for the sake of episode runover rather than anything else. Do we need yet another scene of Data smokin' a 19th century pipe because that's what all the cool androids were doing because they couldn't get lung cancer in doing so? Or Picard reading Data's transfer orders when enough context and exposition were already stated? But other reasons can include a particular scene where the tone of a character's motivations, if not the entire story, is shifted. I just wish I could think of one right now, though "Return of the Jedi" did have a deleted scene about the death star operator getting queasy at having to destroy Endor (the scene of which was removed, not just because it showed "humanity" in the Empire, but because - despite its short length - it altered significantly the plot of the film.
Granted, they could still chop out the second half of the guy's speech where he gives a hooty about the troops on the planet and leave in the rest... but other related scenes also show the sets to look cheap -- so many reasons why the lot of it was chopped out, leaving the bare amount of Palpsy and Luke only in the finished product. The deleted scenes definitely change a lot of the tone of the movie and arguably pointlessly. But I digress, the same concepts are used in tv and movies all over the land.
But that's, so far, just discussing scenes filmed back when the story was scripted. Another fad is to film new material to place into the old story that was never intended. Even Red Dwarf parodied this before it was cool with the series 1-3 "remastering" where they had a sock puppet break the fourth wall deliberately. It was as shrewd as it was dumb, but it's all good. Then you'd be on your way to a "completely separate story".
Never mind deleting a story's scenes to create a new tone or venue - that definitely creates a separate story as a result. Cut out just enough of "I, Borg" and Hugh could stay on and somehow never be detected - the story's writing is so bad and loaded with inconsistencies (situation and character) that a lot of stuff would have to be removed... after which point you'd have a much tighter and compelling adventure, even if it'd be only 6 minutes long (leaving 37 minutes for something far better). But that's an extreme example...