Same issue here (Samsung Note 3), ATT & Samsung are clueless
There is a significant amount of discussion of this issue in the att forums (I can't post links, but it's at https : // forums.att.com/t5/Android/S-Voice-now-Voice-talk-and-non-Wi-Fi-connection/m-p/4053580#M53935). I've been experiencing this for about four days now. S-Voice suddenly stopped working and returned "I can't find a network connection. Please connect to network and try again." This only happens on the AT&T data network; wi-fi works fine. When I called AT&T tech support last night, they actually knew about this issue but had nothing to offer me beyond the fact that it was a "known issue" and that "Samsung is working on a solution." They gave me the number for Samsung tech support, but those folks were less than helpful. At first, they pretended it was an issue with my phone and said I should send it in for repair. He said that there were no other reports of this issue from other users.
Then, when I mentioned that this issue is all over the Internet, the guy said "Well, we have had a 'significant' number of complaints about this, but not a high number." Every time I asked a question ("Do you have an SLA for a resolution?"), he put me on hold for five minutes and came back and asked irrelevant questions. ("So, you say this happened because of a software update?" "No, YOU said that.")
Finally, he said it was an Android issue and that Google is working on a fix.
I have downloaded the S5 version of S-Voice: apart from the ugly colors, it behaves exactly the same as the Note 3 version (i.e, works on wifi and does not work on the mobile network). I also tried changing the APN per the screenshot in this thread, but that did not change the situation.
As a workaround, I'm currently using "S for Switch Voice" (a buggy little app that switches to Google Search every time S-Voice is opened), but I'm really hoping this is fixed soon. Right now, all I'm seeing is finger pointing.