I suspect that evolutionary explanations of masochism suck for the same reasons that evolutionary explanations of homosexuality suck: these sexual orientations are the product of developmental factors, rather than being evolved adaptations. Purely social/environmental explanations are also pretty bad.
Homosexuality is related to certain developmental factors, particularly prenatal hormones. There's some preliminary evidence that masochists are more likely to be queer: BDSM practioners disproportionately report non-heterosexual orientations relative to the general population (one example: this study found rates of 51.9% and 20.6% for female and male bisexuality, which is way above the general population, though this sample wasn't random). If homosexuality is related to developmental influences, and masochism is correlated with queerness, then I would hypothesize that masochism is related to developmental influences, also.
BDSM practioners disproportionately report non-heterosexual orientations relative to the general population
I've always chalked this up to the conjecture that once you've personally accepted, or interpersonally admitted, one minority sexual preference, you're probably more likely to accept/admit others. The effect you cite sounds too strong to be explained just by that, though.
Followup to Stuck in the middle with Bruce:
Bruce is a description of masochistic personality disorder. Bruce's dysfunctional behavior may or may not be related to sexual masochism [safe for work], which is demonized by most people in America. Yet there are ordinary, socially-accepted behaviors that seem partly masochistic to me:
Question 1: Can you list more?
Question 2: Doubtless some of the behaviors I listed have completely different explanations, some of which might not involve masochism at all. Which do you think involve enjoying pain? Can you cluster them by causal mechanism?
Question 3: When we find ourselves acting masochistically, should we try to "correct" it? Or is it part of a healthy human's nature? If so, what's the evolutionary-psych explanation? (I was surprised not to find any evo-psych explanations for masochism on the web; or even any general theory of masochism that tried to unite two different behaviors. All I found were the ideas that sexual masochism is caused by bad childhood models of love, and that masochistic personality is caused by other, unspecified bad experiences. No suggestion that masochism is part of our normal pleasure mechanism.)
Some hypotheses:
My guess is that, if it's a side-effect (e.g., 3) or a non-causal association (4), it's okay to eliminate masochism. Otherwise, that could be risky.
These all lead up to Question 4, which is a fun-theory question: Would purging ourselves of masochism make life less fun?
ADDED: Question 5: Can we train ourselves not to be Bruce without damaging our enjoyment of these other things?