You can change your voicemail tone in your profile setup. can't remember the exact steps.
The icon is a little phone. Its hard to tell but it means that they are either on the phone or for some other reason your message can't be delivered at that time.
Posted from my CrackBerry at wapforums.crackberry.com