http://www.straightdope.com/columns/060203.html
On first encounter this question, which has been showing up all over the Net, seems inane because the answer seems so obvious. However, as with the infamous Monty-Hall-three-doors-and-one-prize-problem (see The Straight Dope: "On Let's Make a Deal" you pick Door #1, 02-Nov-1990), the obvious answer is wrong, and you, Berj, are right--the plane takes off normally, with no need to specify frictionless wheels or any other such foolishness. You're also right that the question is often worded badly, leading to confusion, arguments, etc. In short, we've got a topic screaming for the Straight Dope.
First the obvious-but-wrong answer. The unwary tend to reason by analogy to a car on a conveyor belt--if the conveyor moves backward at the same rate that the car's wheels rotate forward, the net result is that the car remains stationary. An aircraft in the same situation, they figure, would stay planted on the ground, since there'd be no air rushing over the wings to give it lift. But of course cars and planes don't work the same way. A car's wheels are its means of propulsion--they push the road backwards (relatively speaking), and the car moves forward. In contrast, a plane's wheels aren't motorized; their purpose is to reduce friction during takeoff (and add it, by braking, when landing). What gets a plane moving are its propellers or jet turbines, which shove the air backward and thereby impel the plane forward. What the wheels, conveyor belt, etc, are up to is largely irrelevant. Let me repeat: Once the pilot fires up the engines, the plane moves forward at pretty much the usual speed relative to the ground--and more importantly the air--regardless of how fast the conveyor belt is moving backward. This generates lift on the wings, and the plane takes off. All the conveyor belt does is, as you correctly conclude, make the plane's wheels spin madly.
A thought experiment commonly cited in discussions of this question is to imagine you're standing on a health-club treadmill in rollerblades while holding a rope attached to the wall in front of you. The treadmill starts; simultaneously you begin to haul in the rope. Although you'll have to overcome some initial friction tugging you backward, in short order you'll be able to pull yourself forward easily.
As you point out, one problem here is the wording of the question. Your version straightforwardly states that the conveyor moves backward at the same rate that the plane moves forward. If the plane's forward speed is 100 miles per hour, the conveyor rolls 100 MPH backward, and the wheels rotate at 200 MPH. Assuming you've got Indy-car-quality tires and wheel bearings, no problem. However, some versions put matters this way: "The conveyer belt is designed to exactly match the speed of the wheels at any given time, moving in the opposite direction of rotation." This language leads to a paradox: If the plane moves forward at 5 MPH, then its wheels will do likewise, and the treadmill will go 5 MPH backward. But if the treadmill is going 5 MPH backward, then the wheels are really turning 10 MPH forward. But if the wheels are going 10 MPH forward . . . Soon the foolish have persuaded themselves that the treadmill must operate at infinite speed. Nonsense. The question thus stated asks the impossible -- simply put, that A = A + 5 -- and so cannot be framed in this way. Everything clear now? Maybe not. But believe this: The plane takes off.
I'm kinda stuck on the requirements to build a giant high speed conveyor belt that can keep speed with a Boeing or Airbus type aircraft. Given the loading it would have to be a series of gigantic rollers with some type of composite-flexo fabric-belt. I would hate to see the lubrication order on that site. Anywise, I don't think the plane will take off because its not moving forward to cut through the air and reduce the air pressure on the top of the airfoils in order to produce lift . 
