I found out that if you do a master radio reset, by choosing:
Options-
Security Options-
General Settings-
Password- and select "Master Radio Reset" you will be prompted with
"Master reset will turn off the radio and restore factory default settings. Continue?"
Select yes, then it will prompt you for a password. If you have not setup a password for this, use 000000
(don't forget to press the alt button before you enter each zero or it will place a space there ;) then enter.
Once the reset is complete, it should reset ALL your correct services. I had great luck fixing this same issue, and I didn't have to go back to customize any of my created or downloaded themes, etc. It aslo kept my Enterprise server connection intact as well as my contacts, emails, saved stuff, etc. Now my voicemail staus indicator lets me know I have voicemails and how many, like it should. Good Luck
BTW I did this with a Nextel phone 7100i.