Is your GV forwarded to your Verizon number? When you get a GV call it comes through?
I've actually never changed it in settings, I just looked and can't even find that on my phone. I just have GV forwarded to Verizon and have Voicemail set up on GV.
Go into GV online, not your phone/app. Go into settings. Click 'legacy GV'. Now make sure your Verizon number is listed and selected under the phone tab. Click on 'activate GV on this phone', it should tell you that you need to dial *71 and you 10 digit GV number (no spaces or dashes). Once you do that it should work. Hopefully.
I think something changed when the app and interface were updated for GV and Hangouts was updated/changed/phased out.
oh, edit: You may now see GV in the voicemail settings choice but if you don't you should be able to select 'carrier' and change the number to GV, no spaces or dashes.
I've never done that though, I just use the GV app to listen to my voicemail. It should work though. "should"