First, if you haven't done a battery pull, I would try that. If that doesn't fix it, see if the icon might have gotten hidden. Go to the folder it was in and hit menu, show all.
As to your voice mail not letting someone leave a message, if your voice mail is not full of saved messages, then I would call Verizon.