I have to be careful about titles, because if I don't, I tend to call them by their working titles, which do fit into the idea of the story, but can be trouble.
I have a WIP that I call Gemini Warriors, for instance, the problem is that The Gemini Warriors is supposed to be the series title and I'm stuck scrambling for something more original than 'The Gathering' or something.
On the other hand, my Camp NaNo novel is Warrior's Rage, but I refer to it as the Elven Story most of the time without confusion.
I think the worst I ever did was a fanfic that I entitled Hansel and Gretel intending to do a twisted version of the fairy tale, and then ended up having the story be just about kidnapped kids, making the title horribly awkward. Especially given that the sequel to that one might fit the title better.
If it's just a story idea, I tend to follow the "Friends" style, The One With The...(insert key aspect here).