Well, to be honest with you... as annoying and pissing it is to have the "Unfortunately Google Search Has Stopped" problem and Google Now not working properly on its last update, the problem seems not to be as bad to return your shiny new phone to Costco or where you bought it.
This is actually a software problem that Google should be fixing very soon and releasing an update to do so. Bear in mind, also that this very week Google I/O conference will take place in San Francisco and most probably they will release a new Android version 4.3 or 5.... which should include most probably a fix to this.
In the meantime, go to your Play Store, search fo "Google Search" and un-install all upgrade to this app, also disable auto-updates for this app and that should work. I have done it and it is OK (not the latest Google Now..but it works, at least doesn't crash).
During the lifetime of your phone you will encounter bugs in software, as long as they are repaired quickly and there are not impeding the usage of the phone and its critical functions, those are not reasons to return it. My 2 cents.
Originally Posted by ErickE
I tested with a friend who got the GS4 last week from Sprint also. I walked him through all of the steps and his search application did not hang at all after adding a sports team or stock ticker. He was on firmware version MDL.
I took it to the Sprint store (even though I bought it from Costco) and they agreed 100% that something was wrong with it. They didn't want to work on it since I just got it from Costco. They said to just take it back since it's so new.
This morning, I received the MDL update. I applied it but unfortunately, it didn't fix the problem
I called Wireless Advocates this morning (the company that sells for Costco) and they suggested that I go back to the store to return it (even though their instructions that arrived with the phone specifically says Do Not Return To Costco In Case Of A Problem.
So, I'm kind of at a loss. If I root it and try to Titanium to delete it, I'm worried that I will lose any recourse with Costco. Once it's rooted, I am out on my own. I am thinking that I will try and return it tonight and if I am unsuccessful, then I will root it and delete the app.