This happened to me as well this past weekend. Here is what I did:
-I went to the speed dial list and added the number for voicemail to position 1.
-I then dialed it using speed dial 1
-Went back and deleted it from position 1 (the one I added)
Upon rebooting, it had been restored. Don't ask me why, I just happened to try these steps and it worked. Hope it works for you as well.
BB 8100c | v22.214.171.124
PM for PIN