Before telling you the idea, a few sources I used to come up with this idea.
Cave story (great free platofrmer)
Metroid fusion (Gameboy advance)
Halflife.
Soldat.


I haven't thought up a storyline in itself, but here's a general idea of how you can make a great single player platformer. I don't think this exists yet, if it does, please tell me.

Let's say we have 5 different main characters in the game, each with their own strengths and weaknesses.
I came up with the following:
- An agile melee fighter. Can't use ranged attacks like guns, but can move very fast and it has a moderate jump height.
- A shooter. A typical megaman type guy (nuff said)
- A stealth dude. Isn't very fast, but can do a powerful melee attack and it can change into scenery (like a flower on the background or such) and be invincible while changed.
- A flying dude. It doesn't jump or anything, it just flies slowly. and it can shoot in any direction (like a soldier in Soldat).
- A sticky guy. When it jumps and hits an obstacle, it clings to it. This way it can move up a wall or a ceiling. Jumping always releases you from the surface and thrusts you in the opposite direction (ceiling=falling, wall is sideways jump, floor is upward jump). You can also do a jump attack, so you have your basic melee fighter.

That should give you enough diversity in the different characters.
The story starts out with the most basic guy in the game. Let's say the shooter. Like in cave story you can get new guns or upgrade your existing gun as you go.
But.... just to name an example.... you suddenly enter a room where you see a defeated Boss character. Of course the player is puzzled and the answer to his/her question isn't answered.... YET.... A couple of these mysteries occur in the game. Some puzzles are solved allready and you can just walk past a screen without having to do anything.
When you've finished the storyline you can play "Episode 2" and start a new game with a different character. Let's say the agile melee fighter is up next. This guy has different moving abilities so it can reach places the shooter can't and vice versa. In this case this fighter gets to a place the shooter's allready been, but you're there EARLIER in time. The boss is alive now and you have to defeat it. As you leave the room you see a small cinematic of the other guy entering this room, finding a defeated boss.

At some points in the game you can even make a little recoring of the final 10 seconds of your boss battle. When a different character enters at a point it can't be seen, but can see the battle for himself, you can just play the recording from that battle and see how you defeated the boss earlier.

In a way this has been done with halflife. In the first episode you are some scientist who defeats some creatures and has to fight some militairy men along the way. In another episode you play some security guard who happens to pick up some radio transmissions referring to the first episode.

I haven't found any games in which you run through several storylines within the same game. I don't even think the genre exists in which you find parts of your own storyline back.

The easy part of this kind of game is that you only build one world, like in the metroid series. Eventhough many characters start on a different scene, their paths intersect eventually.

This kind of game unravels a huge mystery which is only clear to the player when all episodes have been cleared.

I have a nice piece of intertwining storyline which could make all characters meet up with each other:
4 out of the 5 characters have played their storyline and it basically all ends in the same way. The bad guy of the story manages to capture the heroes and they are all transported to a central chamber where they are trapped in a pod. The bad guy tells them his plan to dispose of them (so you see that bit up to 4 times. After telling him that plan the storyline stops (so you won't see him execute his plan).
Now it's time for episode 5. Surprisingly you are the henchman of the bad guy and you're actually the guy imprisioning the 4 heroes of the previous episodes. But in this storyline you're a person who slowly realises the bad guy is actually not the guy he wants bossing him around.
Somewhere in the storyline you enter the room where the 4 heroes are captured in the pod and again you listen to the badguy telling them his plan. This is the exact spot where you turn good and prevent the heroes from being disintegrated/burned/frozen/sufficated (you think up something) and you press a button which initiates a self destruct sequence and you make a run for it....
Episode 5 can end with the henchman succesfully escaping and making it to some planet.
Now you can add a whole new set of episodes with the 5 heroes with which you just played.
In the very end you can make all heroes meet up with the boss and you can choose one character to fight him.

In the end you can even make a multiplayer game in which you can play these characters (their strengths depending on the choices you made in the singleplayer game, otherwise using a default set of strengths).

Cavestory offers several seperate storylines you can follow, if you do those in a certain way you get different weapons. You can use that here too.

It's a lot of storyline here.. Not saying I want to make a game like this, but I'm just curious of what you think of it.