Western or not is always a good question. When does a western start? I think we had a discussion like this somewhere else. I think back then someone said, a western starts around 1840 and ends somewhere round 1920 or so.
Of course this is no accurate way of telling westerns from other flicks.
Usually for me westerns have got something to do with the so called wild west (which can also be found somewhere in Mexico). It has to do with outlaws, the frontier, cowboys (in a quite open definition) and ingredients like that.
TotSM is a western for me. It is set maybe a bit later than "usual" westerns, but apart from that it has got a real western atmosphere and setting.
Sam Cooper, the SW remake of TotSM has undergone one a few changes in setting and no one doubts this one to be a western.