I looked around the internet for solutions to this problem and everything I found written about it was muddled and didn't really resolve the implicit conflict. I worked through the problem myself and found something that I haven't seen anyone else here mention, so I'll give it a shot. (Feel free to yell if you disagree with my analysis; I'm far from a perfect being.)

Since the two avenues of logic involved are contradictory (that switching cannot matter, and that switching must be in your best interest), clearly there must be an implicit assumption somewhere that is wrong. You KNOW switching can't matter; that is utterly, utterly intuitive and indisputable. However, you also KNOW that given a 50/50 shot of doubling or halving, it is beyond doubt that you should change. Both of those statements seem positively true, and it turns out that they both are. So what gives? It turns out that the key is this:

Your odds are NOT 50/50 of getting a larger or smaller amount if you switch!

Turns out that, magically, it is actually MORE LIKELY that you have chosen the envelope that contains more money. This is, of course, given a couple of reasonable assumptions about the problem.

Assumption 1: The person stuffing the envelopes has a finite (but unknown) amount of money at his disposal.

If you knew the amount he had, it would be easy. If he has only $150 to spare, and you open $100, you wouldn't switch, because you would always lose. If he has $1000, and you open $100, then you would switch, because the switching argument will hold true. It turns out that if you know the limit L, you should always switch if you've opened less than L/2, and stay if you've opened more.

Also, the problem really doesn't make sense if you're working with an infinite amount of money, because for one, all sorts of weird contradictions happen with infinity, and besides, there really is a finite amount of money in the world.

Assumption 2: The person stuffing the envelopes is equally likely to put any amount into the envelopes based on the amount of money he has.

Meaning, if the guy has $300 to work with, he's just as likely to fill them with $100 and $200 as $1 and $2 or anywhere in between.

The problem with 50/50. Let's say, for example, that I am stuffing the envelopes, and I only have $1500 to blow. (The real limit doesn't matter; it only matters that there is some limit, as you'll see.) This means that the most you'll ever see in the envelopes are $500 and $1000.

Say I randomly choose an amount between $1 and $500 to put in Envelope A, and then double that amount and stick it in Envelope B. It turns out that you are twice as likely to open an envelope with $500 or less as you are to open one with $500-1000. The reason is that only B will ever contain one of those higher amounts (since if it was A, and you saw $600, $1200 would be in B and therefore above my means.)

However, either A or B could contain any amount below 500. If you open and see $400, it could either be A you've opened, in which case the other has $800, or it could be B, in which case the other has $200. Since in effect more envelopes (twice as many) will contain amounts in this bottom half, it follows that given a random envelope, two-thirds of the time it will be <$500.

Now that you know this, the math checks out. You pick an envelope. Call x the amount in the envelope, and L the unknown amount equating to the most you could ever find in an envelope. If you just keep the envelope, you have made x, plain and simple. What if you always switch?

Two-thirds of the time, x < L/2 , and you will gain by switching. One-third of the time, x > L/2, and you will lose by switching.

The revised situation: (2 / 3) ((2x + x/2) / 2) + (1 / 3) (x / 2) = x

...and order is restored.