Ok, I think everyone except wow, who is most likely a troll, now understands why the plane would fly if the riddle is interpreted to mean:
The treadmills belt spins at a rate of speed equal to, but in the opposite direction of, the speed of the plane relative to a stationary observer outside the frame of reference of the treadmill, otherwise know as the planes airspeed if we assume a still wind (the planes speed relative to the surface of the treadmill is its groundspeed).
This is the locigal, "real world", interpretation of the riddle based on the actual observatble behaviour of both treadmills (obviously on a smaller scale) and planes. It has been explained to death by everyone on this board and by several outside sources why the plane would take off under this interpretation. This is infact the correct interpretation in that if one were somehow able to construct such an experiment it would correctly predict the result.
Now to the other possible interpretation of the riddle, which I will state as:
The treadmill belt's tangential velocity matches the tangential velocity of the wheels.
First, off I do not believe this is a valid interpretation of the riddle because in order to the conditions of the riddle to be satisfied at all times one would have to assume both a treadmill and airplane engines capable of infinite acceleration. This is obviously not a real world interpretation of the riddle as we have yet to build airplanes or treadmill belts capable of traveling at the speed of light (that whole mass becomes infinite thing is a b!tch).
However, given despite my misgivings of the second interpretation, I will concede that someone could possibly interpret the riddle this way. However, it makes no difference as the plane will still fly. Not in a conventional or controlable manner, but it will infact get airborne.
The reason the plane will still fly was stated earlier when someone talked about velocity boundary layers. As the treadmill moves it entrains some of the air in contact with its surface to move along with it - this is called a boundary layer. Were you to actually construct a treadmill capable of the infinite acceleration necessary to keep a plane with infinitely powerful engines from taking off, the boundary layer of air it would entrain would cause an enormous hurricane of moving air traveling in the direction of the treadmill and over the wings of the plane, throwing the plane into the air. This could only be prevented if both the treadmill and plane were in a vacuum, but then the plane would have no chance to fly even without the treadmill which isn't really fair to the plane now is it.
THE PLANE WILL FLY!!! VIVA LA REVOLUTION!
Note: The last possible interpretation - that the treadmill matches the groundspeed of the plane relative to the surface of the treadmill - is invalid as it postulates a non-inertia frame of reference.