It sounds like the contacts are saved both as Google contacts and sync'ed to verizon. First what I'd do is to log into the phone's gmail account on a desktop and look to see what contacts are there. If they are all listed, then you really don't have to worry. After a reset they will sync back to the phone.
If they are not there then go to the contacts app, press menu>import/export>export to file. It will export a vCard file with all your contacts in it. Then copy that off the phone to a PC. Open the gmail account, go to contacts and click on the more button. Import contacts should be there and give you the option to import a vCard file.