Hey akdodger
You would need to check two places. The first is Settings > Sounds, from there you can change the sound for Voicemail and other alerts. The other section is at Settings > Notifications, from there you setup how to manage the alerts for your messages.
iPhone User Guide
http://manuals.info.apple.com/en_US/iphone_user_guide.pdf
Thanks for using Apple Support Communities.
Regards,
-Norm G.