BRAVO! This fix worked for my Galaxy s3 too!
I spent an hour with Verizon tech where they wanted to upgrade my software causing who knows what to my well functioning phone
I simply needed the voicemail icon on my notification bar.
Follow fix above or to reiterate:
Go into your voicemail, select personal setting option (number 4),
Now be sure you choose to turn "message waiting indicator ON "which means clicking number 1 until the automatic voice prompt confirms that your setting is ON -not OFF
Call your cell phone, leave a message. About 3 seconds later the icon notification appears on your phone.
Voila! a voicemail indicator appeared! I've been without it for a few years now.
To make it go away:
Swipe down to show your notifications list; click on the voicemail notifier, it then automatically dials your voicemail; Listen to your voice mail and delete or save the message on your voice mail.
It is gone. Ready for the next message.
Thank you android central for your great community!!
Important note: in the Verizon voicemail app, via settings-applications manager-ALL-voicemail,the 'show notifications' box is stilled greyed out..... Now not a problem