I think the problem is that westerns are a romanticized genre. They represent an era of wild lawlessness and open spaces, where a man could make a fortune and live and die by the speed of his gun.
The problem with western themed games is that they always boil down to a by the numbers Shooter. Add some horses and a tumbleweed for ambience and thats pretty much it. Unfortunately, few come close to that feeling of Gunsmoke or Bonanza
I think GUN came closer to it than any other game because of the relative "open world".. the problem is it was waaay too small and it all felt forced.
A western game should have wide open ranges and mountains, changing weather for winter and hot summers, buggies to drive, wagons, fighting Injuns, real saloons, mining towns, hunting gathering furs, herding cattle to build a mighty beef empire, or just be a sheriff.
Instead they toss a few activities at you similar to this but it doesnt really satisfy. Gun really did try, but it just felt like I visited ONE town, a SMALL one at that and that I could ride around the entire 'region' in a matter of moments. Thats like having GTA take place on one city block.
Redemption looks good but it has to be careful not to pigeon hole gamers into genre-specific situations that feel very much out of place in a game based on a genre rooted in the concept of real freedom and potential.