For years I've wondered why we don't have encrypting phones.
Five or ten years ago, phones may not have had great processors, and some would argue there wasn't much need. The first issue is quickly dying and the other is thoroughly obsolete.
Demand exists. Maybe it's not huge, but it exists.
Interoperability should be simple. Your phone initiates conversation with a quick 'Know such-and-such encryption?' and if the other phone says 'yes', you trade keys and encrypt (or, I suppose, send your pubkey and subsequently encrypted AES key1). Maybe this means older phones get a couple tones at the beginning of a call. Probably not, but I don't know how they operate.
Phone companies probably like lock-in, so a lone company creating an encryption protocol and releasing a phone probably isn't sufficient. Get some big players on board. Get them all together, create a free, open standard for encryption and agree to all to start supporting it at least on the fast enough models.
Until you do this, I see no need to buy a mobile phone. (If they did this, I'd have a need: to support the concept. Actually, why not release a landline phone for this as well?)
1 Can you get deniability with AES? I've always thought making it illegal to record people talking to me on the phone is really stupid, but if it's something we want, this could be a way to handle it. Maybe doesn't work so well with voice data.