Too bad your game never made it. I would have been curious about the results... Do you happen to have some old artwork or screenshots of what you've made so far? I'd love to have a little more insight of your idea.

The original storyline I had for my idea was the following, but I haven't thought it through yet.

The game would be called "Red X". The game starts with a huge battle between lots of soldiers fighting an even greater amount of robots (or different types of soldiers). This battle takes place at the bay of a huge space ship (the game world, how metroid is that?).
All soldiers are wiped out except for one. He's just on the floor unconscious (the lucky bastard). To make the storyline more interesting he'll probably have amnesia so I won't give away too much of the storyline yet. He gets an order every now and then but due to some radio interference he only gets small bits of information. Later on he finds out the one on the radio is a good friend of his (maybe we can make the friend a female to make it more soapish so the game appeals to a greater audience ).
In the course of the game the soldier comes to some bio-lab where all sorts of different creatures are encaged. The soldier manages to escape a whole bunch of enemy robots/soldiers by releasing the doors of all cages setting the critters free (of course a huge battle between the creatures and the soldiers takes place).
This storyline ends when the soldier is caught (like I said before).

Storyline 2 begins completely different. An infant creature (maybe fuzzy, maybe ferocious) is living at home with his family. On this planet are several other creatures including this creature's friend. This is some winged creature... pterodactyl like. There is a war going on between his village (more like a set of caves) and the enemy village. The war chief wants to plan some sort of assault on the enemy village, but whilst hunting for food our hero overhears the enemy setting a trap. By using stealth he of course plans to go back to the village and warn his friends. When he reaches the village the tribesmen are gone so he has to follow using a shortcut he knows. At the very last moment he manages to warn his friends and so he prevents his own tribe from being wiped out so easily. A huge battle is about to take place anyway, but our hero tries to stop it by standing in between the two tribes. The tribes ignore the poor little critter and run towards each other anyways. By stroke of luck (or maybe not) a bright beam of light shines on top of the critter. The power of the light forces both tribes backwards (some sort of blast effect) and the critter is sucked upwards towards.... something you can't see. You see a fade to black while the critter heads for the sky unwillingly.
A bit later on our hero wakes up in a cage aboard a huge space ship (for those of you paying attention, it is indeed the same place I mentioned before). He's not alone here. Worse yet... There are other creatures there from his planet including one of the rivaling tribe... Immediately a boss battle occurs. As you almost defeat the boss the doors open. The boss character uses this oppurtunity to flee fighting some guards and passing the soldier of episode 1. As the soldier from episode one leaves the hero manages to escape. This hero walks around the ship a bit recieving new bits of global storyline information after which he gets caught too.

The 3rd storyline is different again. This person is more of an anti-hero. This character (let's call him the warrior) has a personal vendetta against the big bad-guy. Don't know why yet... Maybe the baddies blew up his planet to make way for a hyperspace bypass . This guy's story starts when his cloaked ship attaches itself to the huge spaceship and drills a hole in the hull so this warrior can enter. His mission is to assasinate the bad guy and in order to do that succesfully it's best he remains unseen. At some points he has to take out some enemies by force, but mostly he has to anticipate their movement and lay down some traps.
As he passes trough an air vent he overlooks a battle between good and bad soldiers (start of episode 1). A few baddies remain after the battle and they are about to check if any good guys are still alive. The warrior, enraged by the slaughter he just witnessed, immediately jumps out and takes on the remaining soldiers. He manages to do so, but right after that some mysterious shadow comes up to him from behind and knocks him KO. He wakes up somewhere else, but he doesn't know who knocked him out and how he got there. He decides to continue his mission and in the end this person is caught too.

Remember the friend of the critter I mentioned earlier? Well, I didn't do that without a reason. He's the main character of the fourth storyline. Basically he's the best friend of the critter and as good friends do, he wouldn't let him down no matter what. Because he is a flier his story progresses differently. This guy's storyline starts out whith a little conversation between him and the other critter. He has something great he wants to show the critter from ep2. He goes home to get it (fighting all sorts of native animals in the way) and returns only to find out his best friend has gone off to stop some tribal war. He arrives there just as the critter is sucked up by a beam of light. He of course flies after it and manages to enter the ship at the exact entry point the hero from ep3 used. He flies in the stealth ship and goes in via the created hole. He's determined to save his best friend. At a certain point he has to run away from a boss he can't defeat and he bumps into the hero of ep3 knocking him unconscious (yup, the exact same place). Feeling guilty he grabs him and drops him elsewhere. The storyline continues and of course this hero gets caught too.

Now it's time for episode 5. The henchman storyline. His story starts with the bad guy talking to him and giving him orders. Right after that a soldier enters the room and a little discussion starts about why this guy allows the boss to treat him that way. A flashback starts showing him a part of his past where some war just ended as he was a kid. This bad guy took him in and took care of him ever since. He can't remember more.
As the storyline continues he captures the warrior making some heroic statement as to why he fights for the wrong cause. This only raises minor doubt about where his true loyalty lies. Later on he recieves word of some escaped creatures (the very same) and he has to prevent them from leaving a certain hallway. This part of the game becomes some side scroller shooter in which the henchman kills off some creatures. The last creature is of course a boss and as the henchman moves on he finds the empty cages (at this point all heroes who were here have left allready). In the final bit of the storyline he captures all other heroes. Each of these heroes makes a different statement, but the one of the ep2 critter hits him the most. He hears about the bad guy invading his planet and obducting creatures from it. Finally he realizes the same could have happened in his flashback. Returning to the major bad-guy he overhears him monologuing to his prisoners and telling them what he actually did. Of course he's sure of what happened on his planet and he gets a clearer flashback of the battle which took place there. Because of this he decides to press some "CRASH" button because of which the huge spaceship comes hurling down to a nearby planet (the storyline allready explained somewhere this ship was hovering over a planet). As this happens the bad guy sends all available guards after the henchman as he himself tries to escape (This is a nice bit of running action in which I can build a time limit). Finally the henchman reaches a mysterious escape pod, this one looks different from all the others. He gets in and as he heads for the controls he finds a mysterious box labeled "Red X". He has no time to pay attention to that, so he fires up the engines to escape.
Of course a huge space ship crashing down wouldn't be a huge spaceship without some big cannons on it, so in this case the escape pod is shot down, but fortunately it crashes on the planet and of course the ex-henchman is only heavily bruised. At this point you see the henchman lying down and the box labeled "Red X" broken and strangely empty.

Well, this is the starter storyline, if you want to hear more, just ask.