I started something like this a while back. Attempting to stop a Borg battle fleet by igniting a nebula, a Sovereign-Class starship inadvertantly opens a temporal rift to the future - three hundred years more or less. There, the crew learn that they failed - the Borg assimilated Earth and the Federation splintered. The Borg couldn't consolidate their gains though - Species 8472 attacked en mass. When they were gone, the Borg were no more (except for a remnant I intended to surprise the players with...), but the Alpha Quadrant was a mess. Ex-Fed members had become isolationist apart from limited trading. Some had starships, but none larger than an Intrepid-Class ship - the Andorians were the toughest militarily, but had regressed to a hostile state. The easiest options for finding allies were the more pacificist Fed members - the Betazoids and the Vulcans (although the Isolationist Movement had really made strides on Vulcan in the intervening 300 years...).
The problem here is that Trek has much simpler time travel than Andromeda (unless your name happens to be Trance Gemini...), so the players might just slingshot back and prevent the Fall...
"That might have been the biggest mistake of my life..."
"It is unlikely. I predict there is scope for even greater mistakes in the future given your obvious talent for them."
Vila and Orac, Blake's Seven