I have an iPad 3 with 6.0.1 and I tried searching for something in the App store and it constantly gives me this message "Cannot connect to iTunes Store". I can browse apps, see the Top Charts, install apps, view Purchased apps but cannot search. I logged out of my Apple ID from setting and the App store. I reset my network settings. I have rebooted several times. On the same network is my iPhone 4 and it searches fine.