Oh my! That definitely sounds aggravating Doonman! Let's see what we can do to get this resolved. Are you able to access voicemail via home service? Can you manually dial *86 send to access? Please keep us posted, thanks!
Follow us on Twitter @VZWSUPPORT
I had the same problem and tried *86 and was able to set up my voicemail again and the problem was solved. It started when I switched back to an old phone (droid back to apple). The only way to set up my voicemail (which I think was ultimately the issue) was to dial *86 and go thru it that way.