Voicemail: callers say no voicemail set up. Phone will not let me save new greeting gives error 1035

Dial your voicemail by going to the Phone app and holding down the number "1" until it dials out. That will let you set your voicemail passcode and greeting over the phone as opposed to the app. Once you've done that, go back to the app, and your voicemails will be there.