Just an update on this. I had to send in my phone for a dropped screen, with the replacement (repaired per Motorola) I cannot now use AT&T visual voicemail app. It won't start and after a 30+ minute call with AT&T they are saying it's not supported on non AT&T branded phones. What a disgrace. Now looking for other options.
Something isn't right here, it works perfectly on (most) non-AT&T phones, I have been using AT&T Visual Voicemail app since I got my Pure (and before that on my Moto G and Nexus 4), it works fine... AT&T CS has to enable it on your account, you download the app, and that's it... it just works. I have used this app on stock and several custom ROMs with no issues at all.
Permission may need to be manually enabled since the app didn't ship with the phone... Go to Settings - Apps, and scroll down to Visual Voicemail, and click App Permissions and enable five options, then go back a step to the App Info screen and tap Storage, then Clear Data and Clear Cache. Now reboot and try to restart the app.
Also, you must have mobile data service (kind of a given) and the correct APN... Under Settings - Wireless & Network, select More, Cellular Networks, Access Point Names, and make sure "AT&T Nextgenphone" is set (the defaults within it are fine if you haven't messed with them).
If you can't make it work, there is another option... Google Voice can act a your voicemail service, or Google any number of free voicemail services online (some have apps, some use vmail to email), to use them you just set them up and change the call forwarding on your phone appropriately.