I haven't flown UA with a bike in quite a while because of the high fee if you don't manage to get through without charges, but I've successfully flown UA more than once with a soft case without being charged. It's a $50 travel bag from Performance that I upgraded with various foam and cardboard sheets and some $12 wheels bags. I built an internal support from a 2x4 and a fork mount, and it ends up being a lot like the airport ninja a few posts up but for about $150. I might even have an html page floating around showing how to pack it. They usually don't even ask when I check that one.

My GF and I went to Hawaii years ago on another airline with two frames in a Trico Ironcase and the wheels in another box. The person at the next terminal told ours "look up bikes" and my GF said something like "It's climbing equipment" after she started looking, which worked like a Jedi mind trick. She couldn't find climbing equipment in the list, so no charge. On the return it was "What's in the box?" "Camping equipment" "Any fuel?" "Nope" "is it over 50 lbs?" "Nope" "ok". And that was about a minute after the ag inspection had run it through a full x-ray.

AS and WN are by far the best with bikes - AS is now $25 for a bike, and WN is generally pretty lax. A friend and I flew with three bikes and a big wheel box, plus some big duffels and I think paid $100 or $150 (it was a while ago - I think my bike in the soft bag went free) for the lot of it.