I just recently got a Verizon HTC One M8 and I couldn't get voicemail or MMS to work either. While searching I saw your post and was beginning to lose hope but... I just spent an hour on the phone with AT&T and I was able to get voicemail working after they manually set it up to work by dialing the number directly (instead of pressing "1" on the keypad) and I was also able to get MMS working by changing the APN settings and switching to the Google "Messenger" app from the Play Store. If you have confirmed the correct APN then try switching to the Messenger app and hopefully you get it working.