The 4 MHz at 800 MHz that will be available for air-to-ground data, including voice, will be auctioned off May 10, 2006: The FCC issued an order on Dec. 9, which I analyzed back then, that settled a number of auction and transition issues. The auction will allow bidders to bid on a non-overlapping approach (1 MHz or 3 MHz out of 4 MHz in either 1 followed by 3 or 3 followed by 1) or two overlapping 3 MHz swaths.
The order made clear a month ago that incumbent Verizon Airfone, which currently has exclusive use of the 4 MHz, has two full years from completion of the auction to migrate from the 4 MHz down to 1 MHz, which will overlap with at least one of the winning bidders. (The internetnews.com article linked to above misstates that transition period as I post this.)
This two-year period for transition is required in part, I learned from the Dec. order, because Verizon will have to upgrade thousands of planes, including some operated by the government, and may need a good chunk of that period to obtain access to and deploy the new, more efficient gear. Airfone will be allowed to operate its air-to-ground phone service until 2010.
It's awfully clear to me, as it is to other observers I've spoken to, that there's no purpose in a bidder obtaining a 1 MHz slice of 800 MHz. I suspect that two overlapping 3 MHz slices will win, and the government will reap a fairly enormous sum--I haven't seen speculations on dollars, but having a symmetrical 1+ Mbps air-to-ground connection on thousands of domestic aircraft coupled with cellular service operating over that link means that it could be a multi-billion-dollar business over several years.
Cellular issues are, of course, still not settled. Internetnews.com states that cell use isn't included in this auction. That's incorrect based on my conversations with four major operators interested in this auction. This spectrum will be used for in-flight cellular transit (via an onboard picocell) to ground, carried just like other data--it's just a matter of when. As soon as in-flight cellular is approved, whichever companies have the rights to this spectrum will be able to route voice over their existing data connections. Some companies have already demonstrated this.
Interestingly, EVDO Rev. A will likely be used by a winning bidder for the air-to-ground communications as a pure, off-the-shelf data communications standard because it can accommodate a moving plane talking to a series of fixed ground stations.