The Monty Hall Problem - where does our intuition fail us? From Wikipedia :

Suppose you're on a game show, and
  you're given the choice of three
  doors: Behind one door is a car;
  behind the others, goats. You pick a
  door, say No. 1, and the host, who
  knows what's behind the doors, opens
  another door, say No. 3, which has a
  goat. He then says to you, "Do you
  want to pick door No. 2?" Is it to
  your advantage to switch your choice?

The answer is, of course, yes - but it's incredibly un-inituitive. What misunderstanding do most people have about probability that leads to us scratching our heads -- or better put; what general rule can we take away from this puzzle to better train our intuition in the future?
 A: I agree that students find this problem very difficult. The typical response I get is that after you've been shown a goat there's a 50:50 chance of getting the car so why does it matter? Students seem to divorce their first choice from the decision they're now being asked to make i.e. they view these two actions as independent. I then remind them that they were twice as likely to have chosen the wrong door initially hence why they're better off switching. 
In recent years I've started actually playing the game in glass and it helps students to understand the problem much better. I use three cardboard toilet roll "middles" and in two of them are paper clips and in the third is a £5 note. 
A: I believe that it's more a question of logic than a difficulty with probability that makes the Monty Hall solution surprising. Consider the following description of the problem.
You decide at home, before going to the TV show, if you are going to switch doors or stick with your first choice, whatever happens during the show. That is, you choose between strategies "Stay" or "Switch" before you play the game. There is no uncertainty involved in this choice of strategy. There is no need to introduce probabilities yet.
Let's understand the differences between the two strategies. Again, we'll not talk about probabilities.
Under strategy "Stay", you win if and only if your first choice is the "good" door. On the other hand, under strategy "Switch", you win if and only if your first choice is a "bad" door. Please, think carefully about these two cases for a minute, specially the second one. Again, notice that we didn't talk about probabilities yet. It is just a matter of logic.
Now let's talk about probabilities. Supposing that you initially assigned probability $1/3$ to the prize being behind each door, it is clear that under strategy "Stay" your probability of winning is $1/3$ (it is the probability of choosing the "good" door). But, under strategy "Switch" your probability of winning is $2/3$ (it is the probability of choosing a "bad" door). And that's why strategy "Switch" is better.
P.S. In 1990, Prof. Larry Denenberg sent a letter to TV show host Monty Hall asking for his permission to use in a book his name in the description of the well known three doors problem.
Here is an image of part of Monty's reply to that letter, where we can read:
"as I see it, it wouldn't make any difference after the player has selected Door A, and having been shown Door C - why should he then attempt to switch to Door B?"

Therefore, we can safely conclude that Monty Hall (the man himself) didn't understand the Monty Hall problem!
Monte Carlo (Monty Carlo?) simulation in Python:
import random

def rnd_door(doors):
    return random.choice(list(doors))

N = 10**5
switch = True # False to stay

doors = set("ABC")
wins = 0
for _ in range(N):
    prize = rnd_door(doors)
    me = rnd_door(doors)
    monty = rnd_door(doors - {prize, me})
    if (switch):
        me = (doors - {me, monty}).pop()
    wins += (prize == me)
print(wins / N)

A: One does not need to know about conditional probability or Bayes Theorem to figure out that it is best to switch your answer.
Suppose you initially pick Door 1.   Then the probability of Door 1 being a winner is 1/3 and the probability of Doors 2 or 3 being a winner is 2/3.   If Door 2 is shown to be a loser by the host's choice then the probabilty that 2 or 3 is a winner is still 2/3.   But since Door 2 is a loser, Door 3 must have a 2/3 probability of being a winner.     
A: To answer the original question: Our intuition fails because of the narrative.  By relating the story in the same order as the tv script, we get confused.  It gets much easier if we think about what is going to happen in advance.  The quiz-master will reveal a goat, so our best chance is to select a door with a goat and then switch.  The storyline puts a lot of emphasis on the loss caused by our action in that one out of three chance that we happen to select the car.

The original answer:
Our aim is to eliminate both goats.  We do this by marking one goat ourselves.  The quizmaster is then forced to choose between revealing the car or the other goat. Revealing the car is out of the question, so the quizmaster will reveal and eliminate the one goat we did not know about.  We then switch to the remaining door, thereby eliminating the goat we marked with our first choice, and get the car.
This strategy only fails if we do not mark a goat, but the car instead.  But that is unlikely: there are two goats and only one car.
So we have a chance of 2 in 3 to win the car.
A: I find that people find the solution more intuitive if you change it to 100 doors, close first, second, to 98 doors.  Similarly for 50 doors, etc.  
A: The answer is not, "of course YES!" The correct answer is, "I don't know, can you be more specific?"
The only reason why you think it is correct, is because Marliyn vos Savant said so. Her original answer to the question (although the question was widely know before her) appeared in Parade magazine on September 9, 1990. she wrote that the "correct" answer to this question was to switch doors, because switching doors gave you a higher probability of winning the car (2/3 instead of 1/3). She got lots of responses from Mathematics PhDs and other intelligent people that said she was wrong (although many of them were incorrect too).

Suppose you're on a game show, and you're given the choice of three doors. Behind one door is a car, behind the others, goats. You pick a door, say #1, and the host, who knows what's behind the doors, opens another door, say #3, which has a goat. He says to you, "Do you want to pick door #2?" Is it to your advantage to switch your choice of doors? — Craig F. Whitaker Columbia, Maryland

I have bolded the important part of this logic question. What is ambiguous in that statement is:
Does Monty Hall always open a door? (What would it be to your advantage to switch doors if he only opened a losing door when you picked a winning door? Answer: No)
Does Monty Hall always open a losing door? (The question specifies that he knows where the car is, and this particular time he showed a goat behind one. What would your chances be if he randomly opened a door? i.e. The Monty Fall question or what if sometimes he chooses to show winning doors.)
Does Monty Hall always open a door you did not pick?
The basics of this logic puzzle have been repeated more than once, and many times they aren't specified well enough to give the "correct" answer of 2/3.

A shopkeeper says she has two new baby beagles to show you, but she doesn't know whether they're male, female, or a pair. You tell her that you want only a male, and she telephones the fellow who's giving them a bath. "Is at least one a male?" she asks him. "Yes!" she informs you with a smile. What is the probability that the other one is a male? — Stephen I. Geller, Pasadena, California

Did the fellow look at both dogs before responding "Yes," or did he pick up a random dog and discovered it was a male and then responded "Yes."

Say that a woman and a man (who are unrelated) each has two children. We know that at least one of the woman's children is a boy and that the man's oldest child is a boy. Can you explain why the chances that the woman has two boys do not equal the chances that the man has two boys? My algebra teacher insists that the probability is greater that the man has two boys, but I think the chances may be the same. What do you think?

How do we know that the women has at least one boy? Did we look over the fence one day, and see one of them? (Answer: 50%, same as man)
The question has even tripped up our very own Jeff Atwood. He posed this question:

Let's say, hypothetically speaking, you met someone who told you they had two children, and one of them is a girl. What are the odds that person has a boy and a girl?

Jeff goes on to argue that it was a simple question, asked in simple language and brushes aside the objections of some that say that the question is incorrectly worded if you want the answer to be 2/3.
More importantly though, is why the woman volunteered the information. If she was speaking the way normal people do, when some one says "one of them is a girl," inevitably the other is a boy. If we are to assume this is a logic question, with the intent of tripping us up, we should ask that the question is more clearly defined. Did the woman volunteer the sex of one of her children, randomly selected, or is she talking about the set of her two children.
It is clear that the question is poorly worded, but people don't realize it. When similar questions are asked, where the odds are much greater to switch, people either realize that it must be a trick (and question the motive of the host), or get the "correct" answer of switching as in the one hundred doors question. This is further supported by the fact that doctors when asked about the likelihood of a woman having a particular disease after testing positive (they need to determine if she has the disease, or it is a false positive), they are better at arriving at the correct answer, depending upon how the question is phrased. There is a wonderful TED Talk that half way through covers this very case.

He described the probabilities associated with a breast cancer test: 1% of women tested have the disease, and the test is 90 percent accurate, with a 9% false positive rate. With all that information, what do you tell a woman who tests positive about the likelihood they have the disease?
If it helps, here’s the same question phrased another way:
100 out of 10,000 women at age forty who participate in routine screening have breast cancer. 90 of every 100 women with breast cancer will get a positive mammography. 891 out of  9,900 women without breast cancer will also get a positive mammography. If 10,000 women in this age group undergo a routine screening, about what percentage of women with positive mammographies will actually have breast cancer?

A: The lesson?  Reformulate the question, and search for a strategy instead of looking at the situation.  Turn the thing on its head, work backwards...
People are generally bad at working with chance.  Animals typically fare better, once they discover that either A or B gives a higher payout on average; they stick to the choice with the better average.  (don't have a reference ready - sorry.)
The first thing people are tempted to do when seeing a 80/20 distribution, is to spread their choices to match the pay-out: 80% on the better choice, and 20% on the other.
This will result in a pay-out of 68%.
Again, there is a valid scenario for people to choose such a strategy: If the odds shift over time, there's a good reason for sending out a probe and try the choice with the lower chance of success.
An important part of mathematical statistics actually studies the behaviour of processes to determine whether they are random or not. 
A: I think there are several things going on.
For one, the setup implies more information then the solution takes into account. That it is a game show, and the host is asking us if we want to switch.
If you assume the host does not want the show to spend extra money (which is reasonable), then you would assume he would try to convince you to change if you had the right door. 
This is a common sense way of looking at the problem that can confuse people, however I do think the main issue is not understanding how the new choice is different then the first (which is more clear in the 100 door case).
A: Consider two simple variations of the problem: 


*

*No doors are opened for the contestant. The host offers no help in picking a door. In this case it is obvious that the odds of picking the correct door are 1/3.

*Before the contestant is asked to venture a guess, the host opens a door and reveals a goat. After the host reveals a goat, the contestant has to pick the car from the two remaining doors. In this case it is obvious that the odds of picking the correct door is 1/2.


For a contestant to know the probability of his door choice being correct, he has to know how many positive outcomes are available to him and divide that number by the amount of possible outcomes. Because of the two simple cases outlined above, it is very natural to think of all the possible outcomes available as the number of doors to choose from, and the amount of positive outcomes as the number of doors that conceal a car. Given this intuitive assumption, even if the host opens a door to reveal a goat after the contestant makes a guess, the probability of either door containing a car remains 1/2.
In reality, probability recognizes a set of possible outcomes larger than the three doors and it recognizes a set of positive outcomes that is larger than the singular door with the car. In the correct analysis of the problem, the host provides the contestant with new information making a new question to be addressed: what is the probability that my original guess is such that the new information provided by the host is sufficient to inform me of the correct door? In answering this question, the set of positive outcomes and the set of possible outcomes are not tangible doors and cars but rather abstract arrangements of the goats and car. The three possible outcomes are the three possible arrangements of two goats and one car behind three doors. The two positive outcomes are the two possible arrangements where the first guess of the contestant is false. In each of these two arrangements, the information given by the host (one of the two remaining doors is empty) is sufficient for the contestant to determine the door that conceals the car.
In summation:
We have a tendency to look for a simple mapping between physical manifestations of our choices (the doors and the cars) and the number of possible outcomes and desired outcomes in a question of probability. This works fine in cases where no new information is provided to the contestant. However, if the contestant is provided with more information (ie one of the doors you didn't choose is certainly not a car), this mapping breaks down and the correct question to be asked is found to be more abstract.
A: I'd modify what Graham Cookson said slightly.  I think the really crucial thing that people overlook is not their first choice, but the host's choice, and the assumption that the host made sure not to reveal the car.  
In fact, when I discuss this problem in a class, I present it in part as a case study in being clear on your assumptions. It is to your advantage to switch if the host is making sure only to reveal a goat.  On the other hand, if the host picked randomly between doors 2 and 3, and happened to reveal a goat, then there is no advantage to switching.
(Of course, the practical upshot is that if you don't know the host's strategy, you should switch anyway.)
A: I'll quote this great article on lesswrong:

The possible hypotheses are Car in Door 1, Car in Door 2, and Car in
  Door 3; before the game starts, there is no reason to believe any of
  the three doors is more likely than the others to contain the car, and
  so each of these hypotheses has prior probability 1/3.
The game begins with our selection of a door. That itself isn't
  evidence about where the car is, of course -- we're assuming we have
  no particular information about that, other than that it's behind one
  of the doors (that's the whole point of the game!). Once we've done
  that, however, we will then have the opportunity to "run a test" to
  gain some "experimental data": the host will perform his task of
  opening a door that is guaranteed to contain a goat. We'll represent
  the result Host Opens Door 1 by a triangle, the result Host Opens Door
  2 by a square, and the result Host Opens Door 3 by a pentagon -- thus
  carving up our hypothesis space more finely into possibilities such as
  "Car in Door 1 and Host Opens Door 2" , "Car in Door 1 and Host Opens
  Door 3", etc:



Before we've made our initial selection of a door, the host is equally
  likely to open either of the goat-containing doors. Thus, at the
  beginning of the game, the probability of each hypothesis of the form
  "Car in Door X and Host Opens Door Y" has a probability of 1/6, as
  shown. So far, so good; everything is still perfectly correct.
Now we select a door; say we choose Door 2. The host then opens either
  Door 1 or Door 3, to reveal a goat. Let's suppose he opens Door 1; our
  diagram now looks like this:



But this shows equal probabilities of the car being behind Door 2 and
  Door 3!



Did you catch the mistake?

There you go, this is how your intuition fails you. 
Check out the correct solution the in the full article. It includes :


*

*Explanation of the Bayes theorem

*Wrong approach of Monty Hall

*Right approach of Monty Hall

*More problems...

A: In my experience, it is the fact that people do not automatically leap from words to math.  Normally, when I first present it, people get it wrong.  However, I then bring out a deck of 52 cards and have them choose one.  I then reveal fifty cards and ask them if they want to switch.  Most people then get it.  They intuitively know they probably got the wrong card when there are 52 of them and when they see fifty of them turned over, the decision is pretty simple.  I don't think it is so much a paradox as a tendency to turn off the mind in math problems.
A: Haha! Funny coincidence, I was just reading the Curious incident of the Dog in the Nighttime to have stopped at the chapter where the speaker was explaining what the Monty Hall problem was. Here's a nice image about the scenario case.
The intuitive mathematical way how I came to understand the problem: to win after switching, you need to pick the door with either a goat and then switch to the door with the car, as you are revealed one of the goat doors when you choose either one of the three doors. There are 2 goat doors, each with a probability of 1/3. Therefore you have a 2/3 probability of choosing the door with a car by switching your choice (choosing a goat door), greater than the 1/3 choice of winning if you choose to keep your door choice. ALWAYS SWITCH! Hope this helps. :)
A: 
What misunderstanding do most people have about probability that leads to us scratching our heads?

It is not the misunderstanding, it is the reluctance (or inability) to calculate probabilities.

What general rule can we take away from this puzzle to better train our intuition in the future?

Such puzzles are puzzles just because they are counterintuitive.
I'm not in a position to determine a general rule (if such one even exists), and in my humble opinion there is no chance to train our intuition in the realm of such counterintuitive puzzles.
But you may extend your knowledge by study and practice to acquire more tools for solving problems — including counterintuitive ones.

Note:
For solving the Monty Hall Problem it is sufficient to enumerate all possibilities:
Let you chose door $\color{blue} {\text {No. 1}}$ (the $\color{blue}{\text{blue}}$ column in the following table).
There are 3 possible constellations of the (hidden) content of doors
(0 means a coat, 1 means a car):




Constellation
$\color{blue}{\text{No. 1}}$
$\text{No. 2}$
$\text{No. 3}$




1st
$\color{blue}0$
0
$\color{red}1$


2nd
$\color{blue}0$
$\color{red}1$
0


3rd
$\color{blue}1$
0
0





*

*In the 1st constellation the host is forced to open the door No. 2 and you win, if you change your opinion.


*In the 2nd constellation the host is forced to open the door No. 3 and you win, if you change your opinion.


*In the 3rd constellation you lose, if you change your opinion.
All 3 constellations have the same probability, and you win in 2 of them, if you change your opinion.
A: We can understand this problem in a very easy way (indeed, it becomes trivial!) if, instead of 3 doors, we consider 1000 doors. Thus, you choose one door, and out of the remaining 999 doors, the host opens 998 of them. After that, you should change your door, obviously. The host didn't choose that very specific door out of the 999 available for a good reason! A lot of info has been gained by the host's action. The same applies to the 3-door problem.
