Personally, I always thought the best 'supernatural overlay' for a Western setting was that provided in Werewolf: The Wild West. Not the werewolves as PCs, as such, just the whole animist/spiritualist backstory.
If somebody wrote up a similar game for BRP, with a native american cosmological backstory in it and a sense of impending spiritual doom, and melencholy from the building of railroads, etc, then I think there'd be something good to work with right there. Deadlands was sort of like that too, but way too cartoony in feel. I'd like something feeling like Once Upon a Time in the West, or maybe a dash of The Wild Bunch in there too. That is, very stylised, but with a hint of impending death.
'Death of the West' as a theme, if you like.