I've seen this sort of idea posted before, but I figured I'd reintroduce it.
AslanC and I were chatting about my campaign in the making. One of the ideas we talked about a lot, but which I don't think I'll be using (sorry Aslan ;) - though it is a great idea, hence this posting) is an Andromeda-Trek.
I'm not sure which of these are my idea and which are from Aslan - this is just the seed of an idea.
The premise is the Federation has fallen. The Romulans have uncovered the little con-job Sisko pulled on them in "In the Pale Moonlight". I've always been a big believer that Trek shows us those who compromise their ideals always pay a price.
The Federation winds up falling to the massive Romulan assault. The Vulcans and Romulans reunify. However, they can't stay a cohesive empire and shatter into lots of smaller houses - like the Nietzscheans.
The Klingons become a bit like the Magog - think Marauder/holy dudes. One idea I have is they behave a lot like Klingons of the Enterprise-era - more like Vikings than conquerers.
The Ferengi would love life in this period.
So it's something like 300 years in the future. The glorious Galaxy, Sovereign, etc. type starships are a distant memory.
Save for one, some big ship (maybe even Enterprise) has somehow survived and is now in this dark future. The PCs are the crew of this ship - possibly a few of the crew are from the 24th century. Maybe some want to bring back the Federation, others want to carve out an empire. The first adventure can be a battle for control of the starship. Other PCs can be from this era - perhaps part of a salvage team.
One key is that despite the power of the starship, they have but a skeleton crew - perhaps just the PCs. Automation is fine for everything working fine, but it quickly becomes a nightmare. Who do you trust on your ship? :D
Exploration is still a key in this type of game - what has happened to the galaxy? But so is the ideal of Star Trek - somehow showing how knowledge and peace are the answer. Bringing back the ideal of the Federation. Somehow bringing back the Federation, showing that it was more than a dream.
(As for why I'm not going with this, mainly because it is very divergent - my new game, if it all goes well, will be deliberately designed to be something of a "back to basics" Star Trek campaign - get away from the Dominion War, the Borg, etc. and back to the core of Star Trek. But I personally think it is an awesome idea and wanted to share it.)