Samoth: I was thinking of the same approach. And my game is slow paced enough to implement a bit of "lore hunting". Its no where near as fast paced as mainstream shooters like Quake or Unreal Tournament.
But can an arena type game have a good, coherent plot? Because the game takes place in an arena/tournament, the plot has to be about the arena/tournament, which is usually uninteresting. Games like Street Fighter and Mortal Kombat really struggled with their movie adaptations. Has there been good books or movies about arena/tournaments?
The closest I have found to an interesting plot is from a defunct text-based browser game call "Nexus War" that takes place in a version of the afterlife where players become angels and demons locked in eternal battle. I guess I could make the setting post-apocalyptic and players go around killing each other for survival. Or something like "i have no mouth and i must scream" where an evil artificial intelligence enslaved mankind and forced them to fight eternally.