Interesting question!!
Well, a *story* is not always appropriate. Lots of times, it is appropriate, but as you discovered with your Bach prelude, sometimes it just doesn't fit.
The reason why a story didn't fit with the Bach prelude is because that was not what Bach was going for. In Bach's day, they had this idea that a piece of music should communicate one emotion, or affection, and that musical figures could affect the emotions in predictable ways. Triplets, for example, were supposed to produce Joy (Jesu Joy of Man's desiring, all gigues, etc).
So a more appropriate question for a Bach prelude would be, "what affection is Bach trying to convey with this piece?" It's also important to note that Baroque affections are not personal and subjective, but rather are universal and objective. Bach tried to communicate joy in general, not his personal joy. Sadness in general, not his personal sadness. This may seem strange, but if you compare him to someone like Rachmaninoff, who was very personal, you can get the idea.
For example, the Bach Prelude in D major from Book I communicates intense joy in my opinion. Prelude in C major communicates peace, I think. So this is different from a story.
Around Mozart's time, people (like philosopher Daniel Webb) were writing about how pleasurable it was to have contrasts of emotions in music--even to have gradual transitions between emotions. In a Mozart sonata, it would be good then to identify several characters or emotions and see how you can make them contrast. And, since Mozart was such an opera genius, it might not hurt to imagine scenes to go with the music. Not stories, just scenes.
Beethoven was more philosophical and metaphysical. In a Murray Perahia masterclass, he talked about this.
Programs or stories would go better with the romantic composers, I think.
And even some 20th century ones. I know that visualizing Prokofiev's Ist movement of the 7th sonata as a march of the communist army really helped me play it better.