I had a similar problem at first. I had originally setup Hullomail which was intercepting my voicemails so they did not reach VV. I had to reinstall Hullomail and deactivate my Hullomail account. Then VV worked great.
Note* The app shortcut does not display new messages. To display new messages use the VV widget.
this is the version im using. Not sure if it is the same for other versions