Found a similar message when I moved my SIM into a Samsung S6Edge+... It appears the "OLD" Visual Voice mail FEATURE I've had on my account all this time isn't compatible with the newer phones.
When I launched the VVM app on the S6Edge+ it prompted me to change, but always failed to change. Turns go, after going into My Verizon web page, there was another feature on my account that also conflicted. It was the Caller ID feature that showed your Name/Number on other verizon users phones (even if you weren't in their addres book). After turning that off, I was able to change my Visual Voice mail to the new one that works.
NOTE: the "new" Visual Voice Mail feature isn't compatible with the 2013 X *IF* you haven't updated it to 5.1 yet.