Usually inaccuracy in a GPS is caused by a lack of locks on active GPS satellites. Sometimes it can even be caused by inaccurate data on the GPS receiver. Usually, however, the inaccuracy is within feet, yards, and sometimes miles. 500 miles, however, seems a bit much!
Personally I'd try a hard reset of the phone. If that doesn't resolve the problem call Verizon Tech support. They'll most likely send you a replacement phone.