I'm going to have to largely agree with Yahtzee on this one. While I haven't played a one-on-one fighter in a long time, the structure of a linear narrative seems to work at cross-purposes to that of a tournament fighter game. The way a tournament fighter is traditionally structured has the player select a character, then use that character to fight each of the other contestant characters in turn. Trying to make a linear narrative out of this would require a ridiculously long one, since you need to have every character encounter every other character at some point. Granted, the newer tournament fighters' story modes seem to do away with that requirement, treating it slightly closer to how an actual martial arts tournament would be handled, where losing a match would eliminate a character from the competition (though some story modes have characters get fought multiple times).
However, this runs into a different problem. Since a story mode has to follow this closer-to-reality structure for a tournament, it necessitates changing the player character as the story moves along. That runs contrary to traditional expectations with a tournament fighter. Most players, I suspect, want to stick with a chosen charcter; they like their move set, their design, etc. Sure they might be willing to experiment with other characters, but that's for a later playthrough; I can't imagine many of them wanting to change horses midstream, especially multiple times.
To be fair, it may be we just need to change our expectations when it comes to tournament fighters. Perhaps story modes are just something we need to learn to accept as the canon for a given franchises' plotline, and in that plotline, not every character meets and fights every other character, because as Yahtzee pointed out, doing otherwise requires some pretty contrived reasons for two people to try and beat the shit out of each other. The other modes, like an actual tournament mode/tower mode/whatever-it's-called mode would be non-canon by necessity.
If for some reason this couldn't work and the traditional tournament mode HAD to have a narrative to it, then the only way I can see that working is by having separate storylines for each character and calling each one a different timeline/alternate reality where that given character fights their way through the tournament and claims victory. That's going to create one hell of a burden on the writers, having to come up with X-number of unique plots (especially for a character roster as big as the MK franchise's). Also, it's still going to require chosing one of the characters to be the canon victor of a given game's tournament so later installments to the franchise can say who won the last tournament. But how to choose? Maybe the developers can poll the players and have them vote on a canon victor. Or better yet, they can have the players duke it out among themselves over who officially won; if they can agree on how to organize the fights, that is.