You have to hold block as you do it.Or you can do it the extremely hard way and do it while jumping.Hope that clears some stuff up.

Basically, it's a lot easier to perform any Fatality that has "up" in it by holding down the Block button while performing the combination. Don't do this with Friendships or Babalities though, as those only work if Block wasn't used during the entire round by the winning player.