Yes. The plane would most definitely take off.

The thrust applied by a plane is not transmitted via the wheels, rather directly against the surrounding air via the prop or jet thrust. Since the wheels provide only a nominal rolling resistance, their rotational speed will have no effect on the forward velocity of the plane. The only resistance is the air drag and interial load of the plane's mass. The plane will take off as normal.

Zeke

Edit: Further clarification: it is the reltive velocity of the air around the wings that provides lift. Were the air speed greater than or equal to the stall speed, the plane will fly, regardless of velocity relative to the ground. If the flightspeed of your plane is say, 80mph, and you're flying into a headwind of 80mph you will not have any forward ground speed, but you will be able to fly up, down, sidways etc.