Bear with me I'm drunk, and have been for most of my postings on this thread
Kentish,
If the speed acting against the motion of the aeroplane (ie the treadmill) is the same as the speed of the a/c (as the question states), then the forces are equal - therefore it has no forward speed - therefore it can't fly!
The speeds may be the same (opposite in direction but equal in magnitude velocity) but
the forces are NOT equal and are not balanced!
Why? Because the forces are not being applied in the same way.
The "force" from the conveyor belt is only one of two things.
If the aircraft is stationary on the belt (i.e. the engines are off/idling), then :-
1. A force occurs between the surface of the tyre and the surface of the belt, due to friction. When the belt moves, this force will always attempt to spin the wheel, assuming the wheel is parallel to the belt. If the belt is moving slowly enough, without any abrupt acceleration, and without any force from the engines,
then :-
2. The force between the belt and the tyre is "transferred" as a result of the very small amount of friction within the wheel bearings to the whole of the aircraft. This results in the aircraft moving slowly backwards with the belt. This will only happen if the belt accelerates slowly enough as not to overcome the friction present within the wheels and their axles.
As soon as the engines are throttled up:-
1. The friction within the wheel bearings/axles is overcome when the force
between the engines and the air is sufficient. This MUST happen, otherwise aircraft all over the world wouldn't be moving around on the ground under their own power and rolling on their own wheels!
2. Because the friction within the wheels has been "overcome" by the force of the engines acting forwards (the friction still exists, but it is small enough compared to the force applied by the engines to be irrelevant now), there is no way for the frictionary force between the belt and the tyre to be "transferred" to the rest of the aircraft. The conveyor belt now exists solely to spin the wheels of the aircraft, as the engine force has "kick started" the spinning motion of the wheels.
I havn't quite completed Physics A-Level (Advanced Higher up here, way up yonder cold Scotland) and I'm quite
intoxicated so I'm probably wrong and some all-empowering might of higher wisdom will come to disprove me later
But...I think
it will fly! 
By the way, Yorks.PPL posted a relatively simple demonstration of why the plane probably will fly earlier!! It can be seen at http://videos.streetfire.net/player....D-D6BA1A43A06B
For those not convinced by the simplicity of a sheet of paper, an electric fan and a skateboard, you could always try the toy car + treadmill idea, or stick a working model aircraft on a travelator...if you care such! 