I've heard or thought of three possibilities:
1) Changing the future means changing or eliminating future time travels into the past (e.g. the events of "City on the Edge of Forever" or The Voyage Home or "Past Tense" or First Contact or whatever), so that means the influence of those time travelers on past events is changed, and thus the past is retroactively changed. (I'm unsure of this one, because if time branches into two parallel tracks in the future, then time travelers from both tracks should still be around to travel into their shared past. And a number of events in Prime canon are influenced by the actions of time travelers from "erased" timelines, e.g. the "Yesterday's Enterprise" crew saving the Enterprise-C and sending it back with their Tasha Yar aboard.)
2) The Red Matter "black hole" opened in at least two times in the past -- 2233, when it discharged Nero, and 2258, when it discharged Spock Prime. It could've opened other portals at earlier times in the past, and even if no ships came through, the gravitational effects of those portals or the supernova energies they discharged could've affected nearby ship traffic or cosmic phenomena (cf. how Soran's supernovae in Generations affected surrounding events), or perhaps starship crews could've changed course to investigate them, and this could've had subtle influences on earlier history.
3) Quantum retrocausality. One quantum theory says that it's possible for events to be influenced by "advanced waves" in quantum wavefunctions propagating back in time from the future. Generally these advanced waves are cancelled out by "retarded waves" moving forward, but in some cases they might actually be able to affect past events. Since Red Matter is an exotic phenomenon, it might be capable of such weird temporal effects.