Spoilers: (Highlight to reveal)
I can't find a way to like Cyborg Sub-Zero if he's just a blue cyborg basically switching with Smoke. It just sounds so... ... ...
In fact unmasked Sub-Zero is my favorite character of all mortal kombats and that version is likely written out of existence.
Contrary to popular opinion, Deadly Alliance's unmasked was my favorite. It captured to a T of who I think Sub-Zero is. A cold, stotic Clint Eastwood type personality that's extremely independent.
http://www.mortalkombatonline.com/content/games/mkda/subzero/
But back to cyborg Sub-Zero, how is Sub-Zero suppose to get out of being a cyborg without making the whole Lin Kuei automation process look weak?
Theoretically, I'd want anyone automated to not be able to return back to nomal. Automation should alter the whole. I'd think an automated individual wouldn't eat, drink or even breath, being that oil and powercells charge their body.
I can't decide if I hate this or killing Kitana off more. EDITED a few sentences afterward.

Spoilers: (Highlight to reveal)
For example, Liu Kang. I am so glad for that scene where he denounces Raiden as having lost his mind and turns his back on the Thunder God to focus on the wounded. He's not simply the de facto champion of Mortal Kombat that we never really "met" or interacted much with in the past. Here, we see him go from being the collected Shaolin champion to becoming angry at the losses sustained in battle against Shao Kahn, and turning against the guardian of his realm in disagreement with his methods.
I honestly can't wait to see how Liu Kang develops from here - assuming he's still alive, which I'm kind of unsure about. And I used to find Liu Kang incredibly boring. I can actually relate to his anger about the situation. Who wouldn't be pissed off that the Earthrealm guardian was handing them all over to Shao Kahn, let alone having tried to use their souls as a bargaining chip in negotiations with HELL?

Spoilers: (Highlight to reveal)
Smoke. Yes, yes, YES. Finally, some backstory to this guy besides, "He was Sub-Zero's friend, became automated, presumably struggles with his humanity in his endings." I'm surprised they actually revealed his nationality, which is something I've seen revealed for a few characters - it's very cool that we have a character from Europe.
You may complain, "Where's the tragedy of his story, now? He doesn't get automated!" Well, from what they reveal in his bio, he was brutally murdered in his youth, returned, and then found friendship in an increasingly hostile Lin Kuei with Sub-Zero. His best friend, who later is captured and automated by the Lin Kuei.
This isn't a simple switching of roles. We never often saw Sub-Zero really suffering over what they'd done to his friend. Here, when history changes, we see Smoke lament what they'd done to Sub-Zero, remarking that it was "hideous".
From all of this, I think Smoke remains a tragic character in spite of not being automated himself. This is the kind of struggle we now see in Cyrax, who - canonically - DID eventually reject his cyborg nature. We also see it in Sub-Zero, who - like Cyrax did - undergo a procedure to attempt to restore his humanity.

Smoke has new traumas and struggles in his human backstory, I'm not going to cry that someone else is bearing the distraught cyborg burden.

Spoilers: (Highlight to reveal)
Sub-Zero. Yes, I was kind of wary of the Cyborg thing, too, but I get the feeling that this isn't going to be a permanent fixture in his future storyline. They've already partially restored some of his humanity, I imagine he's not too far-gone. With Smoke at his side, enthusiastic assistance from Jax and other Earthrealm combatants, and games of development ahead of him as one of MK's leading characters, I'm sure that we'll see him return to human form fairly soon in the future.
I'm very happy to have seen him interact with Smoke, and to see how his quest to honor his brother panned out. The revelation that his brother became a Netherrealm revenant in the service of Quan Chi and how it parallels his own loss of humanity was actually fairly poignant and paves the way for him to be a heroic and wise character down the line.

Spoilers: (Highlight to reveal)
Kabal and Stryker. Now THAT was something I wasn't expecting, but thoroughly enjoyed. Stryker's bio presents him as an obvious mixture of the lead characters of Die Hard and Speed, giving him at least some credibility as a "tough cop" archetype from the get-go. But seeing him and Kabal working together in the police force caught me off-guard, and it's great that Kabal has been returned to his roots as a veteran of the Black Dragon that has thoroughly rejected his criminal past. Except now, not only has he rejected it, he's taken up the exact opposite career in his determination to make up for his poor choices.
He even gets a scene with Kano, who - surprisingly - greets him as an old friend and is relatively cordial with Kabal. I know they obviously have some history together, but it's neat how NRS had him attempt to approach Kabal in the guise of an old friend, rather than the typical Mortal Kombat, "We're on opposite sides, and that's all the motivation I need to kill you right here!" Kano demonstrated some savvy in trying to play up character ties.

Spoilers: (Highlight to reveal)
The treatment of a lot of the villains and their chronology. As Razor pointed out, Baraka and Ermac being present from the beginning is going a bit far. Ermac, I can somewhat accept, though I would have preferred to see him later on. Baraka should have made his original appearance attacking the Shaolin temple - which seems to have still happened, but off screen.
The worst offender is Quan Chi. I'm a big fan of Quan Chi, and I'm well aware that the canon places his role in the story before even the first tournament. But to have him as a combatant and a known presence to the other characters from the very beginning pushes it. Part of his appeal to me was that he was behind the curtain pulling the strings. Now, we see a lack a subtlety as he blatantly uses Scorpion as an enforcer and seems more cocky than he usually is portrayed as being.
But... Well, he's Quan Chi, and I liked the scene where he blows off the attempt by Raiden to get the allegiance of the Netherrealm against Outworld. Also, his presence and the glimpses of Shinnok clearly indicate that we're going to see Mortal Kombat 4's storyline rewritten and fleshed out in the next game. Given the lost potential of the original game and how Shinnok failed to have much of an impact... I'm looking forward to it very much.

While Mileena's introduction is certainly fudged up from the original, the discovery that she exists actually plays a pivotal role in Kitana's turn against Shao Kahn, and we finally know exactly how Shao Kahn regards the both of them. This was one aspect of Shao Kahn that I was curious about, and while it didn't quite play out like the predictions I'd read and loved, it's a positive point I can draw from a screw-up.

Aside from chronological issues, I'm rather annoyed that Baraka and Reptile didn't get much development and remain functionally the same as they were. The same goes for the Shokan characters, who get a bit more backstory, but are only seen in the story mode as one-dimensional henchmen.

Spoilers: (Highlight to reveal)
Kung Lao and Kitana's deaths. I'm not opposed to characters dying, but I feel almost cheated when I read the text and they just get their asses handed to them. It heavily reminds me of the Conquest television series - the deaths were shocking and brutal, but they leave the audience feeling empty. Kung Lao spent much of the story in the background, while Nightwolf seemed to take his place. And, once again, in some deference to Shaolin Monks, he seems motivated by the desire to best Goro in the name of his ancestor, which doesn't really strike me as enough to want to cheer his character on. So he dies, lacking in development.
Kitana, on the other hand, goes through her story arc, and suddenly perishes in battle with her mother. It's the opposite of Kung Lao's situation - he had too little character development for his shocking death to resonate any more than hollow, and she's had too much character development to die already.

Actually, as a side-note regarding Conquest: This story is very similar in some regards to the television series. Raiden's submission to Shao Kahn very strongly recalled memories of that last episode, where he is worn and defeated in body and mind by the destruction Shao Kahn's forces unleashed on Earth. Here, his portrayal is quite similar to the Conquest version, incorporating elements of the distant god-figure of the original MK1 story and the Dark Raiden of Deception and Armageddon. This isn't a complaint by any means, because I enjoy me a flawed Raiden, but it's interesting how the game story is very reminiscent of the television show...

Spoilers: (Highlight to reveal)
Some of the character endings are awful and obviously non-canon. Jax and Kano's really bug me, because they're not very relevant to the story at all. A lot of the villains get the typical "Betray Shao Kahn, become all-powerful" endings they had in MKs 2 and 3. Though, not all of them are completely bad, and some are quite intriguing in some ways, such as Sonya's and even Liu Kang's - though I'm very glad THAT one isn't going to happen.
- Nightwolf's was cheesy, and I'm not a fan of Noob's - I detest Havik, and his ambitions are tired and disappointing.
- Johnny Cage's was a complete "What the fuck?" I get the sense they're trying to imbue him with some sort of supernatural powers from his biography in this game, but the Randomly Exploding Johnny being sent to Seido is ridiculous.
- Jade's ending certainly raised a lot of questions that I'm not expecting to be answered, but I have the feeling that this is NRS showing us that the One Being mythos hasn't been forgotten.
- Raiden's ending was underwhelming, given his prominence in the story and his goals. Assembling the Power Rangers of the Winds isn't exactly where I imagined him going...
- Stryker and Sheeva's endings were hilarious, I loved those little touches.
- Is Kabal's ending a tongue-in-cheek reference to the Six Million Dollar Man?

Spoilers: (Highlight to reveal)
I personally hope the game is setting up for the epic invasion that MK4 should have been. I've always felt that MK's netherealm was a VERY pale comparison to what the christian idea of hell really is, I.E. eternal pain, torment, gnashing of teeth...etc. If I could get a little taste of that combined with the stories and interactions of the MK kast, especially Tanya, then I think that alone would merit the changes to the canon. That's just me, though.

Spoilers: (Highlight to reveal)
My only semi-irk with the whole thing being Mileena having just been created. But to me that's nothing major. Just not a lot of time to flesh out her story. And I don't get why people are making a big deal out of what they call Sonya's "daddy issues." And I think some posters referred to her as crazy. I think that's bullshit, myself. It takes nothing away from Sonya's character, and if anything, just fleshes her storyline out more. Proves that she's not some raging bitch, that she actually has feelings. Really humanizes her.