What I understand happened in Prisoner's Paradox is that the very field of probabilistic distribution of pardons has shrinked from 3 to 2. It's like binary search. You cheated your way by knowing where _not to look_.
Another simple analogy: you can increase the value of rational number both by increasing the numerator and decreasing denominator. In this case you decreased denominator.
Monty Hall requires a slightly bigger leap of logic.
Actually, here's a more directly linked problem: http://en.wikipedia.org/wiki/Three_Prisoners_problem
Prisoner A rejoices that his own chance of survival has improved from 1/3 to 1/2. But how is this possible? The guard has given him no new information. Has he?
No, Prisoner A still has a 1 in 3 chance of [edit: not] dieing. If he asked if Prisoner B had a pardon then you could argue his odds became 1/2. But, now he still only knows that at least one of his cellmates is going to die.
This isn't the same as Monty Hall. Monty Hall only increases the odds after switching doors. This actually seems like a trick meant to fool people who know about the Monty Hall problem but don't really understand it.
I re-read all three problems after you replied and this is what I understood. Talking about Three Prisoners' problem since the article's wording doesn't include the very crucial ingredient for easier understanding: coin flip on warden's side.
For A, it doesn't really matter if B or C were executed. In fact, he knew that either B or C are going to be executed for sure. He knew that at least one person who is not him will be executed.
Warden just named the sure-to-be-executed-guy. Didn't change what he previously knew about his chances, since he still doesn't know for sure whether the-other-not-named-guy is going to be executed.
However, the distribution changed for C. Now A still knows that there 1/3 chance of him living but since we know for sure that the-guy-who-warden-named (B or C) will be killed the-guy-who-warden-didn't-name-and-who-isn't-A (C or B) will have 1 - 1/3 = 2/3 probability of living.
So when the guard says B is sure to die he is actually opening door number 2 to show no prize is there.
Before this event the odds of survival for each prisoner were 1/3, 1/3, 1/3.
The odds that the guard would choose prisoner B as the non-surviving one (dead that is) in case prisoner A/B/C is the surviving one are: 1/2, 0, 1.
That is if A was pardoned then the guard can chose either of B or C so the odds of pointing out B are 1/2. The odds of pointing out B as dead when he is pardoned are 0 and the odds of pointing out B as dead when C is pardoned are 1 (because he cannot indicate A as dead because the guard is not allowed to tell A about his own fate). Hence the final odds for each prisoner must add up to 1 so through proportionality they are 1/3, 0, 2/3.
So prisoner A didn't find out anything new about his chance of being the pardoned one.
That prisoner should immediately switch name-tags with the other prisoner who's fate is in question :)