The voice mail tone is pretty much what your SMS tone is. There's a way to change it. I don't remember exactly how though. Someone might be able to post the link.
Go to your profile menu, scroll down to 'advanced options' them go to the profile type you want to modify, then change the types of message tones, not sure what the voicemail tone is under, but yet there.
Posted from my CrackBerry at wapforums.crackberry.com