One thing that you can try is to update your roaming preferences by dialing *228 and selecting option 2. After that do a restart and see if makes any difference. Doing this lets your phone seek out cell towers closer to you.
- Also, check the verizon coverage map in your area. The less red spots you see around where you are could mean that the coverage may not be that great.
- Are you able to connect to WIFI? Do you notice significant speed differences in browsing or with other apps that require internet access?
Current ROM - Cyanogen Mod 7.2
Flashing rule to live by: Always remember to wipe Cache and Dalvik Cache!