The description says that I have to complete 20 story missions without switching to a new horse at a hitching post. If my horse dies, and I wait for a respawn, will it be considered a "new" horse? Or can I still get the achievement?
Unfortunately it doesn't count. You MUST play the story missions with the SAME horse. In the other hand, you must do this with STORY only missions. If by some mean you end the game you will have to start it again to get this trophy. (Replaying story missions doesn't count). This makes this trophy the only one you can miss.
By the way, there are a total of 57 story missions.
According to the PS3 Trophies guide, as long as you don't change breed of horse when it dies, you should be able to collect the achievement.