Two possibilities are first you have auto sync on with either Verizon Back Up Assistant or iCloud auto sync.
In the first go in to My Verizon and enter back up assistant and remove the entry and then send a sync command to the phone. You can also delete the contact via long press then go into Verizon Back Up Assistant App and send a sync command to remove it that way. For the record I don't use the verizon backup but the Apple icloud http://www.icloud.com
I access from my computer and remove the contacts or make new ones then sync that way. if you have auto sync to icloud on in your iphone a long press select delete the phone will auto sync when its plugged into a power outlet on schedule. It can also be done manually.