It's all pretty much true - in the sense that yes, the airlines are paranoid but also yes, it's possible for cellphones to interfere with avionics. As a flyer I'm fairly happy for airlines to be paranoid about this.
Also phones so high in the air and moving so fast could really screw with the network
- they can be "seen" by too many cell towers, causes problems with interference and paging
- they move too fast through the network, it's hard to hand them over between cells
Keeping a call going to a plane which can "see" perhaps 100 cells and is moving at 500 mph is really hard. The whole network is designed on the assumption the user is on the ground and so can "see" only a handful of cells, and is moving at <200 mph. Also your phone is in an almost perfect metal box so it's hard to get the radio waves out.
Making 2G phones work with 200 mph French TGV trains was a pain in the butt, let alone 500 mph planes.
So the ban on cellphones in the air is probably paranoia, but even if they lifted the ban tomorrow you would still really struggle to make calls from the air, and/or the network would hate you for screwing lots of other calls up. Unless the plane has a picocell as a previous poster said.