Right now, the mobile industry's in a state of change. European GSM networks are having UMTS (3GSM, "W-CDMA") networks added to them, the US GSM networks plan to replace their networks completely with UMTS (the other widely used standard in the US, IS-95 (CDMA2000, "CDMA"), isn't really open in the same way as GSM/UMTS is/are. An IS-95 customer can't just buy a phone compatable with the network and activate it themselves without the phone company's involvement and permission. If Apple used that, they'd lock themselves out of the rest of the world, and reduce their markets in the US to only those phone companies that actively cooperate with them.)
There are some hold-ups however. The main one is that the way UMTS was originally specified relied upon the fact countries had generally agreed to make available certain spectrum for 3G. It was assumed it would run in addition to existing GSM networks, rather than on top of them. In the US, the FCC has (for largely legitimate reasons) taken its time getting the relevent bands cleared. The result is that Cingular, the major GSM network in the US that's moving to UMTS right now, is having to overlay UMTS onto its existing network, using non-standard frequencies, which will probably change once the FCC clears spectrum for 3G. But, hey, even that's not clear: once the FCC does this, it will probably want to auction the new bandwidth, which will mean more 3G operators.
To work around the difficulties getting UMTS implemented, GSM has been enhanced with a system called EDGE which implements somewhat faster data rates and slightly more capacity. Both T-Mobile and Cingular have widely implemented it, but the rates aren't that fantastic, comparable, perhaps, to ISDN, and that's when the network's not congested.
It's kind of convoluted, and the market itself is a little difficult to judge while this is going on. Apple can just produce a GSM EDGE phone, but it would be slow (especially if the aim is to provide downloads from the iTMS) and, to much of the world, look outdated. A Sprint/Verizon IS-95 hook-up would lock themselves (and their customers) out of the rest of the world. A UMTS phone would lock themselves out of most of the US right now.
Oh, and one other thing, margins on cellphones are razor thin. There's too much competition in the area. And it's very difficult to persuade people to buy unsubsidized phones in most countries, some parts of Europe excepted.
If I were Apple, I'd wait.
If I were Apple and couldn't wait (worrying that MP3 playing cellphones with hard drives were about to hit the mass market), I'd go down the MVNO route, at least in the US, probably with Cingular. I would go with UMTS, because (a) it's backward compatable with GSM and any phone built today that uses that standard will need minor tweaks to stay up to date and (b) Most UMTS operators are likely to be keen to see a return on its UMTS investment and, while they'll want to see a large amount of per-customer income, the traffic charges can be small given the increased capacity. In the US, I'd sell only in Cingular UMTS markets, and keep the device and service low profile nationally until Cingular has rolled out their UMTS network to enough of the country.
To protect Apple's reputation for simplicity, I'd go for a pre-paid service model, preferably using something that hasn't been used before (in the US, at least.) Maybe $500 for the device (iPod nano 4Gig + phone) and unlimited domestic voice/message usage for a year? $2 per song downloaded (including data traffic charges)? With a model like that, it wouldn't be necessary to lock the phone, which in turn means that people who would prefer to use the phone with a different carrier can still buy it.
All in all, I don't actually buy the rumour at this point. It's an awful time to launch. Regular cellular service, as people are used to, is generally priced in an entirely opposite way to any of Apple's regular businesses (subsidized equipment that sells usage charges, rather than locked usage selling hardware), and as such the above model, which I rather like, would represent a large gamble in terms of customer acceptance and yet is pretty much the only way Apple could go from here without building a massive new business that operates entirely unlike the rest of Apple. And the technology to build it upon hasn't been rolled out and will be significantly tweaked over the next few years in ways that aren't completely predictable.
For now, I vote "No" on this happening, at least in 2006. Maybe late in 2007.