I've also successfully used Kalen's bike bag. It's really just taking the stem, wheels, rack, and derailler off. Fork stays, it's not so bad. Went out to RAGBRAI free with the Tardis on AA even though I had to take it to the oversized baggage window at SeaTac. The counter in Des Moines tried to charge me for it but I pulled a "well it was free coming out" and got away with it. The point of the charge is because they're expecting a normal big bike box that requires manual handling. If they just load it onto the conveyor belt behind them don't pay the fee!
If you don't mind even more disassembly (fork removal--you've got a sealed bearing headset right?) it's not hard to out of a bike box. Basically cut off the long end at ~41inches and fold the new ends in to make it shorter. The bike pictured (57cm) fits in the box pictured. I got it down to 66 linear inches. Soooo close to airline standard 62.
However note the fail as Joby mentioned that I didn't flip the box inside out first and it has bike shit all over the outside. Great for customs, bad for arguing I shouldn't be subject to a surcharge.
Also, put your u-lock in your checked baggage. A TSA goon had a problem with mine but thankfully his supervisor didn't!