You have to define what you are trying to protect and against whom. There are several assets:
- Your geographical position
- Who you call and who calls you
- The contents of your conversations and SMS
- Your phone bill
Then things are quite different, depending on whether the phone operator is a cooperative friend, a not-too-competent neutral third party, or an active attacker.
The phone bill is the simplest. If the operator is an attacker, then you are doomed. The theoretical countermeasure would be a tamper-resistant phone which records usage in a way which could convince a judge; I do not know of anything like that, although most phones keep a log of the most recent calls. If the operator is not an attacker, you have to trust the operator for not being hacked, and you also need to avoid your phone getting hacked, too. Smartphones, being full-fledge complex computers in their own right, with one or several network links active at all times (think about Bluetooth...), are susceptible to external hacking. So a non-smartphone may be advisable.
Anonymity concerns (geographical position, who you call and who calls you) are a hard problem. I heard that in some places, police services use cell phones to keep track of protesters in manifestations: a fake base station is setup, and broadcasts a big fat message of "I am the most powerful base station here, all phones in vicinity are to report immediately", and all the phones gladly answer "I am here !". If that situation is a concern for you, then you will need to "rotate" through numerous, short-lived receptors and accounts (obtained with fake names, of course), so this is expensive; and you will not receive calls, unless you use some VoIP software inside a VPN (so the operator sees that you connect to the VPN, but not what exits at the other side of that VPN).
A famous example of an anonymity concern, involving a satellite phone, occurred in 1996 with somewhat drastic consequences.
For the conversation contents, this is a question of encryption. In GSM phones, an algorithm called "A5" is used, with several variants: A5/0, A5/1, A5/2 and A5/3. A5/0 is "no encryption at all". A5/2 is "weak encryption", meant for export to countries of questionable reputation. A5/1 is a stream cipher which uses a 64-bit key but is actually weaker than that, with protection around 242.7 (the number may vary depending on how you count and some operational conditions such as the size of known cleartext; see this article for some details); that's much too low for comfort, so it should be assumed that the contents of A5/1-protected data can be learned by determined attackers (the Wikipedia page on A5/1 also cites some cracking efforts based on rainbow tables). A5/3 is also known as KASUMI and comes from the UMTS and GPRS worlds; it has some weaknesses but nothing fatal so far.
In any way, A5 encryption is only from the mobile phone to the nearest base station, so if the operator is an attacker (e.g. you are trying to evade legitimate eavesdropping by law enforcement agencies with which operators cooperate), then A5/x will not help you, regardless of what 'x' is. To survive that kind of attack, you need end-to-end encryption, which in turn requires a change of protocol, hence VoIP with custom encryption. An existing product is Zfone, from Phil Zimmermann (of PGP fame).
The biggest security conundrum here is that the standard protocols being quite bad at ensuring your security, you need a smartphone with custom software to obtain a reasonable level of protection; but security of the phone itself is also of paramount importance, and is much easier to achieve with a dumbphone.