I'd suggest give players checkpoints across the maps that they can respawn at after they die. Give them unlimited lives (or at least more then 1), but also give them a time limit to get to the end, because this whole 1-life-then-gameover thing kinda...well...sucks.
-VGsatomi