I think that before speculating about the selection pressure leading to religion, we should ask whether religion arose as a grass-roots phenomenon, or was usually imposed (or suggested, like a fashion) from the top down. The former case would lead you to expect religion to provide a general selective advantage. The latter only requires religion to provide a selective advantage to the religious elites.
What made me think of this was discussions with a Catholic theologian, which uncovered 4 irreconcilable points between us. All of these points are arguments in which theologians wish to use God as an extralogical operator to get them out of conclusions that are unacceptable to them. Most religious people have never even thought about these arguments, and have emotional reasons for being religious. If religion came from the top down, I might argue that religion is the "logical" conclusion of primitive logic; this argument would not be tenable if religion is a grass-roots phenomenon.
Followup to: Rational vs. Scientific Ev-Psych, The Tragedy of Group Selectionism, Evolving to Extinction
Perhaps the real reason that evolutionary "just-so stories" got a bad name is that so many attempted stories are prima facie absurdities to serious students of the field.
As an example, consider a hypothesis I've heard a few times (though I didn't manage to dig up an example). The one says: Where does religion come from? It appears to be a human universal, and to have its own emotion backing it - the emotion of religious faith. Religion often involves costly sacrifices, even in hunter-gatherer tribes - why does it persist? What selection pressure could there possibly be for religion?
So, the one concludes, religion must have evolved because it bound tribes closer together, and enabled them to defeat other tribes that didn't have religion.
This, of course, is a group selection argument - an individual sacrifice for a group benefit - and see the referenced posts if you're not familiar with the math, simulations, and observations which show that group selection arguments are extremely difficult to make work. For example, a 3% individual fitness sacrifice which doubles the fitness of the tribe will fail to rise to universality, even under unrealistically liberal assumptions, if the tribe size is as large as fifty. Tribes would need to have no more than 5 members if the individual fitness cost were 10%. You can see at a glance from the sex ratio in human births that, in humans, individual selection pressures overwhelmingly dominate group selection pressures. This is an example of what I mean by prima facie absurdity.
So why religion, then?
Well, it might just be a side effect of our ability to do things like model other minds, which enables us to conceive of disembodied minds. Faith, as an emotion, might just be co-opted hope.
But if faith is a true religious adaptation, I don't see why it's even puzzling what the selection pressure could have been.
Heretics were routinely burned alive just a few centuries ago. Or stoned to death, or executed by whatever method local fashion demands. Questioning the local gods is the notional crime for which Socrates was made to drink hemlock.
Conversely, Huckabee just won Iowa's nomination for tribal-chieftain.
Why would you need to go anywhere near the accursèd territory of group selectionism in order to provide an evolutionary explanation for religious faith? Aren't the individual selection pressures obvious?
I don't know whether to suppose that (1) people are mapping the question onto the "clash of civilizations" issue in current affairs, (2) people want to make religion out to have some kind of nicey-nice group benefit (though exterminating other tribes isn't very nice), or (3) when people get evolutionary hypotheses wrong, they just naturally tend to get it wrong by postulating group selection.
But the problem with this hypothesis is not that it's "unscientific" because no replicable experiment was proposed to test it. The problem is that the hypothesis is, as a matter of prior probability, almost certainly wrong. If you did propose a valid experiment to test it, I would expect it to turn up negative.