I believe "Moon River" by Henry Mancini was another example of this, Genie. Can you imagine "Breakfast at Tiffany's" without it?
Going back to the original point, I often find that it takes several attempts to make a song work. I do mainly originals (cos I'm not much good at covers). I think that the first couple of times that I play a new song, I just am not playing it well enough to move an audience much. That comes with practice like anything else. You have to give yourself a chance to get good at performing a song. It doesn't mean there is anything wrong with the song itself just because you are not able bring it off at the first or second attempt.