Voicemail notifications are actually communicated via SMS (SMS's primary purpose is for simple background communication between the network and the handset, including setting and clearing "voicemail waiting" flags. Using it for customer messaging was added quite late in the GSM specification). So there is a technical link between SMS and voicemail, but I can't imagine the sort of technical fault which would reformat every incoming SMS as a voicemail notification.
Which leaves another possibility: there are services which will turn SMS into voice messages (I've one friend who consistently sends texts to our landline, and this is the result). I presume you have checked whether there actually are voicemail messages? I'm not aware of SMS apps that can automatically forward incoming SMS elsewhere, but it might be worth checking there isn't anything like that in your settings.
Whatever is going on, if this is affecting all incoming SMS (rather than just from some people) I think the most likely place for the problem is your service provider's systems. So I agree with Danny, you should speak to them. I suspect this will be something that the first-level customer support won't have a clue about, so it may be a long call (and be aware that it's likely that their support script will rapidly lead to the question "have you done a factory reset?" - which is not an unreasonable thing for them to ask when faced with weird #$!£ that nobody has ever heard of, so don't get annoyed if they do).