I have had my storm for a few months now and I have never had this problem until now.
I realized I hadn't been receiving any voicemails and yesterday my phone just sends me a notification that I have 18 voicemails dating back from mid-Feb to now. I re-installed Visual Voicemail and that seems to work better.
However, now my SMS icon has dissappeared from my homescreen and I cannot receive any text messages. I have sent a few from other phones and am not getting any of them.
