It sounds like the voicemail service failed or is stuck in some fashion. The easiest thing to do is to reboot the system, which should restore voicemail functionality. If thats not an option, we have other things we could try, but the best bet is a reboot.
To answer the second question, we'd need to know what area your in.