Few people know that your cellphone can be reprogrammed when your in a "dead-zone" and it will search for nearby towers. According to one source, your phone gets used to keying in on certain towers in areas you frequent.
Verizon---*228, hit send, follow prompts, let phone reset. Others, You'll have to contact your carrier to see what to do.
I've found if you stop before you get into the known deadzone, and reset, your phone works better. Not always, but, hey worth a try!