I'd go as far as saying that this question makes your interviewing process to be more "cheat-friendly" - the chances of an interviewee not knowing of the problem and solving it on the spot are a lot lower than those of him having heard of it and pretending to solve it on the spot.

The first time I heard of it I was surprised about how counter-intuitive it seemed, but it didn't baffle me completely because I have a strong information theory background. From an information-theoretical point of view, it's not completely counter-intuitive that new information can change probabilities a posteriori, particularly when there is mutual interdependence.

To be fair most explanations of the Monty Hall problem gloss over the most important fact, that Hall knows the correct answer. When I first learned about it I had a hard time comprehending it until I very carefully reread the description and realized this key fact.

I can't remember where I read it (or I'd provide a link) but the real "a-ha" moment for me came when I read "... so what if there's a million doors instead of 3? Does that make a difference" (it doesn't to the argument but it does to most people if you frame it in that way allegedly) in an explanation.