ive had that problem with a few nokia phones. it may be the phone OR it could be a cingular voicemail upgrade issue. get another phone and see if the icon appears on that phone, if it does, youll know that its no the e398