It doesn't appear right away. You have to unlock it just like the other 2nd fatalities. The code unlocks the ability to do the fatality. The input is Down, Up, Up, 3 (triangle on PS3, Y on 360) from jump.
I kind of have the same deal. I redeemed the code for the scorpion classic costume and fatality, but I don't see anything on the PS3. How do I even wear the costume?