1. First sign out of your account in Google Voice on your cellphone.
2. Then reset your voicemail on your cellphone by pushing ##004# then "send" so that it goes back to your cellphone provider's voicemail service. (NOT SURE THIS DOES ANYTHING ON VERIZON-GOT CALL CANNOT BE COMPLETED AS DIALED)
3. Make sure voicemail service is set to "my carrier" in "settings" on phone.
4. Check to make sure the number for voicemail is the one for the cellphone company in "settings" of your phone. This is 805-637-7243 for T-Mobile (*86 FOR VERIZON). Enter the right number if it is not there.
5. Sign into Google Voice on phone and choose to have Google Voice as voicemail.
6. Check "settings" on phone to make sure the number was changed to the Google Voice number.
7. Then, by going to "settings" ON PHONE, NOT THROUGH GOOGLE VOICE, change voicemail service to "my carrier."
8. Check to make sure the voicemail number was changed back to the cellphone company's in "settings" on phone. If it is working, then the number should be changed.
9. Open Google Voice on cellphone. Sign in if prompted. If you are already signed in, sign out then sign back in. Choose Google Voice for voicemail.
10. Check "settings" on phone to make sure the voicemail number is now one for Google Voice.
Your voicemail should now stay with Google Voice even after restart.
IMPORTANT: If you sign out of Google Voice on your cell before step 7, this will NOT work. There is an option inside of the Google Voice program on your phone to change voicemail back to your cellphone carrier. NEVER USE THIS!!! If you use this, this will NOT work and I believe this is where Google Voice screws up. You must go to the "settings" from OUTSIDE of Google Voice, i.e. the android os/home screen.
If you want your voicemail number back to the cellphone carrier's number even after restart, follow step 7. If you change inside of Google Voice it will NOT work and the number will go back to the Google Voice voicemail number after restart. Finally, if it does not work, try repeating the steps. Hope this helps.