I'm a firm believer in the idea that you should not have to get a special app just to do edit basic phone functions. And it's possible that I have a found out how to do this for you without downloading an app.
From the home screen do the following:
* Open All Programs
* Scroll to the bottom and open the Voice Mail app. Green icon.
* Press Menu
* Settings
* Scroll to the bottom
* Voicemail Notification Settings > Notification Sound
Try changing this and testing it out. I have not since I already like my sound (DROOOIIID). Good luck.