There is a setting in the phone that dictates where the voice mail goes. I don't know how to get it back though without doing a factory reset. Probably have to input some service codes to do it.. You should be able to call ATT and have them help you reset it.
If you have you mail installed still there is a button to deactivate it. If you already uninstalled it the go to your phone click on settings buttons go to call settings. Then click on voicemail settings. You will need to find someone that has the same carrier to find the service number that you need to input.
Well now that a YouMail rep is here, how about telling me why it keeps logging itself out and not notifying me of voicemails until I open the app and login again? I'm pretty close to going back to AT&T voicemail too.