Voicemail notification icon should be automatic when you get a new voicemail, the icon will show up in your banner and you should get a notification in your messages application as well. No setup required!
A voicemail notification will come into our sms folder in which case you need to call your voicemail in order to hear it. The tone will be the same as sms.
Posted from my CrackBerry at wapforums.crackberry.com
I do get the icon but it doesn't have an audible notification .Im sure it used to beep when there was an voice mail .
You might try going into your Profiles, open up sms alerts and see that the notification is not set to silent. That is what a voice mail is set to come in as.
Posted from my CrackBerry at wapforums.crackberry.com