The story line, such as it is is indeed pretty weak. It's not totally unsalvagable, but considering the work it would take, I dunno. Here's my take on the discussion so far though.
Even with a social group as large as the GTVA it's not impossible or even really improbable that radical changes in government could take place in a relativly short period of time. Volition did it with the Vasudans and the Terrans not far prior to the present game timeline if you need a canon reference.
Here's something else I'm going to point out: A lot of people continue to say that the GTVA military was decimated (referring btw to having one in ten of a military force destroyed, not one in ten surviving), however in the game itself, reference during the campaign is made only to a few of the GTVA military's fleets engaging in combat: 6th Terran Fleet, 3rd Terran Fleet, and the 13th Vasudan Battlegroup. There is little mention of the other fleets, and none that I could find of any others engaging in the current conflicts.
The NTF gained much of its resources from the 6th Terran Fleet which was commanded by Bosch before the rebellion, though the unit still existed as a GTVA fleet during the campaign. It is unclear what other units, if any he may have co-opted. He did have access to at least one shipyard however, so it would be realistic to expext the rebels would have at least some new construction.
There were only a handful of systems involved in the NTF rebellion, and only one populated system invaded and destroyed by the Shivans. Though this left Capella's population temporarily homeless, it is rather silly to think the refugees would not be granted homes in the systems ravaged by the rebellion, as the extra manpower would be needed for rebuilding, and therefore most welcome.
As far as the large number of new ship classes, actually with the large number of conflicts in a relativly short time frame, it's not so unfeasable. You need only to take a good look at naval design evolution during WW1 and WW2, and the between war period. There were numerous new ship designs of all classes during each time period. They were spurred on by the conflict, rather than being retarded by it.
The generally ineffective management of all conflicts fron the Terran-Vasudan war to present by Volition's canon governments would be plenty of reason for rebellion/reform. Incompetence by those in power usually leads to their loss of that power.
EDIT: AlphaOne, I'm going to make a suggestion to you. It's not a flame, but some constructive criticism. You need to improve your writing skills. I'd suggest taking classes if you are truly passionate about telling a good story. Your story ideas are not exactly origional from what I've seen. They have a very childish quality to them. While this is not necessarily a really bad thing, it doesn't really work well when writing about war, even a science fictional war. A final suggestion as well, take the time to study your subject. read up on the history of major conflicts. Reality is stranger than fiction, and an excellent place to draw your inspiration from. This will help you mature as a writer.