You could try this VZNavigator .cab.
I don't use VZ Nav., so I am not sure if this will work for you or not. Just uninstall, if it doesn't function for you.
I also attached the latest Visual Voice Mail from Verizon.
VZW_VisualVoiceMail_1_1_11_65.cab (2.26 MB, 59 views)