Any good VZW tech can give you the following advice:
Turn off the automatic network time adjustment. Use another phone to call & leave yourself a message. Wait an hour, then you can turn the auto network time adjustment back on. If you still have the same problem, rinse/repeat.
There are some phones, BlackBerrys & iPhone being the most prominent, where VVM & auto network time sync just do not play well together. So you might end up having to leave it off & adjust your own time periodically.
Posted from my CrackBerry at wapforums.crackberry.com