@westenra, if you don't want to actually record your own voice, name, and greeting, to actually skip all of that.
When it asks you to say your name, tell it to start recording, but don't say anything and quickly press the button to stop recording. The system will complain that your recording is invalid but will continue to the next step of telling you to record a greeting message. It will tell you something about using your voice to say your phone number out loud if you don't feel like recording anything. You don't even need to do that. Just tell it to start recording and quickly tell it stop without saying anything. The greeting will be set to a preset default greeting that reads your phone number out.
To my knowledge, the voicemail account doesn't have to be setup for people to leave you messages.
What I would do is call your cell phone number and leave a short randon voice message for yourself.
Then, using your cell phone, call in to check your messages. It will insist that you set everything up at that point. Listen, and delete all messages including the one that you left for yourself. After doing that, I believe that the new voice message icon will clear.
