Do a hard reset. Go to your Setting Menu, and then Privacy, I believe. Do that and it should be good.
But yes, VZW will do it for you, but you don't want to take a chance. You may want to change your GMail password afterwards, as well. Just for safety in case some way is found around a hard reset to get old info.