It's not a Big Red issue. I worked VZW Tech Supp until about a year ago. VZW literally only provides the data link on this issue. If you're not having data issues with anything else, it's a GV issue. The old standby for this is uninstall the GV app, then reinstall. If issue persist, try changing the settings and then change them back. Outside of that it's all GV. GV isn't known for addressing issues that they don't find themselves, or seem to impact a lot of people. Apple is just as bad if not worse for trying to pass the buck back to service providers. BB was great, they'd take anything.
Have you rooted?