Master, the batteries of your telephone are almost completely depleted!
As for Story Mode, I wouldn't know what to expect. Hopefully it's not as hideous as SSE though.
I suggest a 70% probability that you should recharge your phone.
That's the same person that thinks Jumpman and Mario are separate characters, so no matter what she says it's going to most likely be a load of rubbish.
Yeah tell me about it, you would think I'd be prepared for this kinda thing now considering how many often it happens to me. It's what I get for not charging my phone overnight, I had nothing to do the rest of the train ride 'cept look out the window and ponder.
Anyway, going back to this...
My thoughts on story:
If you're gonna do it, do it right, but it shouldn't take away from the focus of the franchise: fighting.
Storytelling is an art, and it isn't a necessary component in gaming; therefore, if you can't get it right, then just scrap it and drop the idea.
Presentation:
First and foremost, no cutscenes and minimal to no voice acting. Both are huge memory hogs and the resources are better applied to something else. Visual Novel style CGs and text will get things across much better than cutscenes, plus you give players something else to collect.
Also by making all character interactions text based, you give yourself the opportunity to hide some interactions in the story and thus encourage replayability and exploration (see Sengoku Rance as an example (I know I don't shut up about this game, but it really is an overlooked gem)). The only cutscenes you should have in the game should be for stage/level introduction like in Melee's Adventure Mode.
VN-style CG's work best because they allow characters to shine as they truly are, because they allow text, you could add some small grunts and voices for characters that could use it, like Snake for example (Super Mario Bros. Z anyone?), and it doesn't bore the player with campy looking, long-winded action sequences, whatever action is chosen (for rival battles and such) can be drawn into a neat little CG that is more fun to admire than having to put up with a Cutscene that's either hit or miss.
Gameplay:
The platforming from Melee Adventure, and SSE was good, just make it more like Melee and less like SSE, include canon characters from each franchise instead of original characters.
Also, I'd say something like a Super Mario World level select type deal for each character would be good, it could allow for neat secrets and branching paths. Each level should be as long as the ones in Melee's Adventure mode, no more than 3 or so mins per level, each one being different depending on what Universe you're crossing and who's going through it, toss in a couple bosses, some crossovers and some secret bosses and bingo.
Short and sweet but different characters should crossover to different universes, I'd say a good 4-6 platforming levels per character, each one with combat areas like in Melee Adventure, 4-6 forced battles (1v1, 2v2, FFA, Survival, Mutli-mans, etc...), 2-3 bosses, a rival battle or two, some challenge levels (Target test, Escape! (the Metroid one in Melee), Race to the Finish (F-Zero one was awesome), as well as some new creative ideas would be neat, you could do stuff like "find the treasure" as a callback to the Kirby inspired SSE, destroy 'X', wreck the car

, etc...), and a character specific endgame boss.
You add some branching paths, as well as hidden battles, hidden encounters with funny dialogue, hidden treasures and trophies, and some hidden bosses. Each character's route shouldn't take more than 1 hour to complete, 2 or so if you're going for 100%. Beat all the Endgame bosses and you unlock a FINAL route like in Sonic Adventure 2, where like in SSE, you choose a group of 4 characters (so you can Co-Op it), take on a simple level, a la Megaman, a boss Rush, and the FINAL Boss.
Oh, and for the record, you should be allowed to save mid route for each character. Meaning, you can do half a route, save, do someone else's route, then go back and continue where you left off in the last one without a hitch, this will also be good for when going for 100%, and the SMW style level select makes it easy to replay levels.
Story:
In my opinion, the only way you can introduce so many characters, and still let them retain their original identities is by having a sort of "Crisis on Infinite Earth" premise. I would say the best example is in Kamen Rider Decade to be honest. But keep it simple, I would say a la Blazblue where you play out each character's perspective.
The story itself shouldn't be too serious nor too convoluted, just **** goes down and they encounter each other, fight and try to fix it. It should be lighthearted and exciting, like an adventure, but not campy, SSE's biggest problem was that it tried too damn hard to be EPIC, and that ruined it so much.
Also, characters shouldn't group up like in SSE, that was awful imo. The story should just serve as a way of presenting character interactions in a crossover, e.g. how would Snake react when meeting Samus, or how would Ganondorf reach when faced with Marth instead of Link, etc.... Characters that can talk in their canon, should speak through text. Characters that don't simply react like Mario does in his RPG series, the world responds to them.
By having separate stories for each character, you give the characters their independent freedom, and still stay close to the canon, rather than creating this ****ed up world where every Nintendo character presumably lives in harmony. Not to mention this perspective based, asymmetrical form of story-telling can be very interesting as you don't ever get the full picture until you finish every route, which motivates the player to continue playing, just to see other Points of View. Also, by making each route different, you remove the redundancy found in Melee's Adventure mode, but also keep it short and sweet, unlike SSE which was more tedious than anything.