Originally Posted by oakie
with a new phone, it's "learning" local tower information. VZW can also push a location update to your phone so you dont have to wait for it to "learn".
Getting a current PRL (Preferred Roaming List) is part of the activation of any phone on the Verizon network, so given that he's gone through multiple phones in a month or so, there's virtually no possibility that this has anything to do with it.
To the OP: You're sure it's not a low battery indicator on your headset (assuming you're using a bluetooth headset)?
Do you, by any chance, have "Privacy Alert" enabled under Options | Sounds in the phone application?