I saw similar post about this problem from 5 days ago (8/15/13). That is also when S-voice stopped working on my Samsung Galaxy S4, even though it was working perfectly for the past 3 weeks. My internet connection is working.
I spent 1 1/2 hours with AT&T Tech Support and Samsung Tech Support on 8/17/13 and they could find no problems with my phone settings or internet connection. However, Samsung tech suggested doing a master reset on my phone. I did not do this yet because I do not believe it is a problem with the phone, especially since I now see another posting for the problem occurring on the same day.
Is this a problem with an AT&T Server or is it Samsung? How can we get someone to check this out?
UPDATE 8/22/13: I spent another 2 hours on phone 8/20/13 with new Samsung tech. He was convinced that it was not my phone after he also checked all the postings about this problem online, so he "elevated" the "ticket" to a "system" problem. Yesterday evening, I found that my S-voice just started working again!