at&t visual voicemail DOES work on the GPE edition of the s4.
Ensure you are NOT connected to a wifi when setting up and it will connect and download.. I kept getting the check network/APN settings.. but I read somewhere that it doesn't work when connected to WIFI.. Sure enough, I turned it off and it immediately configured and downloaded VMs.
Very strange but it is working great now ( as long as I am not on wifi
Mike