I noticed after my post I'm not the only one with issues. Mines in the iTunes Store search, not apps, and on ipad 3, not on iphone. And I'm not a fan of all these DFU mode things...seems a patch for what is a bigger issue. I tried all of the easier suggestions all to no avail. I have other iPads working just fine.
I've been able to get everything else to work but search. And I can subvert that problem by going into Safari and putting into search for whatever song or group "on iTunes" and it gives me a link to it. By clicking it, you can get into iTunes for some of the items, but not all. And if you try to navigate around from that, you can get around but a new search locks up again. So I'm not totally out of commission. I'm not risking hours of restore work or time for the patch work efforts like DFU mode, etc. or going to apple and hear the proverbial "oh we haven't heard about this issue,". Seems a waste of time. Apple should have heard this by now and know of it and try to figure it out. Especially when some posts find it fixes itself.