Because of the controls that were in place with the carriers at the time, and the fact that Apple didn't want to operate under those controls, it was not easy for Apple to find a company to work with. On top of that, there was no guarantee the iPhone would be a success, and it also required significant change to the software operating the cell towers, for things like visual voicemail. And also, Apple was asking for a lot of money.

ATT was supposedly not Apples first choice, but it was the one that accepted the conditions Apple bought to the table.