One of the biggest drawbacks of MKA for me, is that there are so many fighters, that you waste time going back to the menu-screen and loading, just to try out a fighter's special moves. But in MK Deception they had enough memory to load two fighters at a time for one player Noob-Smoke.

My proposal, team all of the characters in pairs, so switching styles switches player, and make the weapon moves, into special moves.

Sub-zero/Scorpion.
Kenshi/Ermac.
Liu Kang/Kung Lao, etc.

And.. have best of one round, not two, but give each player a seperate health-bar. i.e. if you play against Mileena/Baraka and you defeat Mileena, you can do a fatality on her, and then fight Baraka, or you can give her a Mercy, by letting the timer run-out, leaving her in the background, and if you also defeat Baraka, you're pair(if both are still alive) can do a Friendship(your two offs their two).

You can also do individual fatalities, like Noob-Smoke in Deception.

Also allow the programmers as many cheap special move combos as possible. MKII was fun because you had lots of fun(albeit cheap) combos.

And pair all the boring characters together, would make them more interesting, or easier to avoid all-together.

Most people complained about Noob-Smoke, but pairing fighters is the only way to make the characters seem real, like they actually know each other.
With 64 individual characters, there's no 'Unity'.

That's my suggestion for current generation, Mortal 2 Kombat.

Also, why not have only 30-40 good 'movie' fatalities, but every character can do 4 of them that, ones that fit their personality.