I've read one simple rule for determining if the work is science fiction or not: if you can take out the science fiction element out, and still have the same story, it's not science fiction. For example, if it is science fiction just because it's happening on a spaceship, and could just as well be happening on a seventeen century pirate ship and still have the same premise, it's not really science fiction. However, if you take the sci-fi element from, I don't know, Invasion of the Body Snatchers, you just don't have a story anymore. That's true science fiction.
I guess the same could be said for true fantasy: if you can take out the fantastic elements and still have a feasible story, it should not be called fantasy, IMHO, although fantasy is somewhat more flexible in this regard than science fiction. You can have worlds similar to ours with no magic or supernatural elements in it, and still call it a fantasy, because sometimes that world is the point of the story.
However, the borders are being redefined every day, and things that pass as science fiction and fantasy today would never have passed fifty or thirty years ago. Eugene Mirabelli's "The Woman in Schrodinger's Wave Equation" was nominated for Nebula in 2008, even though it has no science fiction elements at all, not a drop. There are more and more examples every day. So in the end, it's all up to the author, market, readers, editors, publishers... But like I said, a lot more can pass for fantasy today than it could fifty years ago. A lot of readers today prefer "soft" fantasy rather than full blown Dungeons and Dragons type of story. Guy Gavriel Kay's books, for example, have very little magic or other fantastic elements in them, but rely on elaborately developed characters and story instead. Still, you couldn't take the fantasy part out of them and still have a plausible story. Even though most of his books are based on real world countries during real historical periods, it's still fantasy because you can not take the characters and the plot and fit them in those real world countries and turn it into historical fiction, because for historical fiction you'd need real historical characters and events. Events that take place in real historical setting but have never actually happened are still fantasy.
So, in the end, I'd say, if that fantastical element, how ever small it might be, is something that would break the whole story if taken out, I'd call it fantasy.