When you start trying to pin these types of questions on "actual" problems you get tons of non-answers. You get distracted, easily. They start worrying about things like libraries, and language issues, and implementation details, etc, etc. And when you try to focus them on the algorithm portion of the question, they get flustered and feel like they are screwing it up.
There is a time and place for stripping away the computer and asking about simple algorithm development to see how people think. People who get offended by abstract problem solving are sending out red flags.
In my experience, however, most questions are either riddles which you get or don't, or so contrived they'd be easier to explain formally. Good story problems are like rare gems.
Beyond that, phrasing something as a story doesn't solve the problem of people nitpicking, it just changes what they nitpick about. Just read the comments on a blog I wrote a year ago about the lightbulb puzzle: http://20bits.com/articles/interview-questions-two-bowling-b...
For me it boils down to this: I'm interested in good problem solvers, not good puzzle solvers. Being able to solve puzzles is at best a weak indicator of being able to solve problems. I'd rather spend my time looking for stronger signals.
But... there are questions that sound very similar to such questions that are perfectly legitimate analogies to various computer science topics. Yes, you might say, "so ask me in computer science terms, not knights and dragons". And my response would be "Why? Do you have trouble with abstractions?". When I mention knights and dragons I'm making it very clear that the answer doesn't require some nuance of the C standard library or some knowledge of the JVM. I'm emphasizing the -abstract- part of the problem, for a reason.
Not to push my own blog but I wrote about this exact topic at length: http://lbrandy.com/blog/2008/09/here-be-the-code-monkeys/