I could not beat that last secret battle at the Warrior's shrine with Kung Lao to save my life (one against Scorpion, Sub-Zero, Ermac, and Reptile). I think the best I ever got was through Reptile and Ermac a couple of tries, but I could never beat either Scorpion or Sub Zero. I saw a vid on Youtube where someone beats it with Liu Kang. His uppercut and bicycle kick look extremely useful in this battle. I just either wasn't good enough with Kung Lao, or his attacks just aren't as useful in trying to beat the four of them.
I also found the fight against Kano and his Black Dragon clan particularly frustrating as well.
But the game itself was awesome. I'd pop it in now but I'm trying to go back through on Dead Space to get ready for Dead Space 2