Is your phone not holding calls where it previously had a strong signal? If you have a CDMA device like those found on Sprint and Verizon, you may need to update your Preferred Roaming List (PRL).
The PRL is a list that allows your phone to roam off of towers that are not part of your native network, such as a sprint phone connecting to a former Alltel tower if none of its own are available. Because roaming agreements are constantly changing and new towers are added all the time, it's important to keep this list up to date.
For most CDMA carriers (including Verizon), you can update your PRL by dialing *228 and selecting the appropriate option. For example, on a Verizon phone you dial *228 and then select option 2 and listen to the horrible programming music while your phone downloads the latest PRL.
For Sprint, there are two options. The first is to contact Sprint Customer Service and get your account approved for an update and then dial *2 and follow the instructions. If you have an Android device, you can also check your PRL by tapping Home > Menu > Settings > System updates > Update PRL. (Thanks milominderbinder)
With Verizon prepping its LTE launch and Sprint lighting up new WIMAX markets, both carriers are spending a lot of time and resources ensuring their current 3G networks are optimized. This means a lot of adjustments to which towers cover a specific location, as well as the addition of new towers to handle additional traffic. Because of this, it's a good idea to update your PRL at least once a month so your phone will always have access to the best coverage available in your area. [Via Android Central Forums]