That's normal behavior until it gets a GPS fix.

Have you ever gotten a fix with the GPS before? If not, the first fix can take up to 3 minutes to achieve, particularly if you don't have aGPS in your area or a recent QuickGPS download.

Grab GPSTest, if VZW installs QuickGPS then run it, then step outside and run GPSTest. You'll be able to see whether you're even seeing satellites using that app, as well as the state of the GPS fix (you're looking for "3D"). The first fix can be painfully slow, then they'll drop pretty quickly since you'll be doing a warm start instead of a cold start.