This method has been tested on a Sprint SPH-L720T on Lollipop, it will probably works on other models too.
1) Dial ##3282#, tap on EDIT, enter the MSL our app retrieved.
2) In each category, delete any references to Spint/Sprintpcs and also change any Sprint IP’s to 0.0.0.0, or left the field empty.
3) Open voicemail, go in Settings/Call/Voicemail. Change the phone number with the one of your new operator.
Credits to our fried Dave!