That thread down there I started a long time ago, Fresh Ideas, discusses this very thing. I think the conclusion everyone came to was that it's nigh impossible to come up with a 100% new idea, and trying to do so might be counterproductive, as you'd be focusing more on novelty than trying to write a decent story.
Anyway, I'm seeing flaws in my logic in that first post; even QM was based off of celestial mechanics and thermodynamics. The new idea introduced there was a last-ditch effort on the part of Max Planck to fix the math so that it fit with observation. Hence it's based on orbital mechanics and observation, and isn't completely new and original. Everything is linked to something else, so that ideas build off of each other to advance one particular line of thought. That's how it's done in the human brain, so there's no shame in building off of a cliché idea.
Though there is shame in re-writing a cliché idea without changing it.
What I would suggest is to go the rare route; in other words, if you write a fantasy novel, set in a place akin to ancient Mesopotamia, or Africa during the Stone Age, or a tribal community in Siberia, or northern Canada in the 1950s, or modern day Afghanistan, or underwater, in space, at the center of the Earth, in Heaven, etc. etc. You know; anything but medieval Europe. Take the road less traveled. That way you win because people will still be able to relate to it, but you'll be doing something that seems much more original.