Delete the contact off the phone. Log into your Google account via gmail, and click the Contacts link. Edit the contact there to remove the *67 and save. Resynce your contacts on the phone (Under Settings, then accounts, click google, uncheck and recheck both to force a resync). Check in your contacts to make sure the changes are there.
Also, if you've used verizon's backup assistant, make sure to do a new backup with that, since it may overwrite your contacts (heads up, it's pointless since everything's backed up to your google account anyways).