Just ran into this issue with Verizon yesterday... I ran into the Store to get it fixed... they tried a few things, but of course this is a NON-VZW phone. I was even on the phone with their tech support because the store reps did not know what to do... finally I left with advice to do a master reset... and I did it... still did not fix the problem, so I went back into the store again and told their main rep I wanted a new SIM card since it did not make sense that I could not call voice mail or call my own number (each time it did the same thing, immediately hung up), it could call out to other numbers and it could get incoming calls.
Finally the main rep (manager) came back over and was talking to me while I was waiting for a rep to free up... he was talking about VVM. VZW had made a change to their systems and have going to this new system without charging the users like they did over the years. I said I'd seen something about this after doing the master reset and I declined it since I did not want VVM. We finally found it in the phone app, behind the voice mail tab. He said it was now free, so I accepted the message their, and it came back with there was an issue with it and I needed to talk to their tech reps and had a link to call them, he said to do that in the store... I did and the rep fixed it from their end... they called me back and left a message, I could hear the message, they called me back a minute later, and everything was working.
It appears you have to use their VVM to get to your voice mail now. Some new technology... I'm guessing it's easier and you can't go back to the old system anymore... NO MORE *86.