I am also having the problem of "Cannot connect to iTunes Store".
I would contact Apple support about this, but I am not sure I can face the legendary arrogant and unhelpful response fron the iTunes team (yes, I have been subjected to this on so many occasions that I am willing to state this publicly).
On my iPad2 when I click the STORE button in Newsstand I get the error "Cannot connect to iTunes Store". However, everything works just fine when I click STORE in iBooks, or go to Newsstand in App Store, or go to any option in iTunes, or click STORE when I am in the Music app: These all work fine and give me access to the iTunes Store. So, it is only from within Newsstand that I find this annoying error.
I have checked my AppleID and password, I have hard rebooted my iPad, and have checked that Restrictions are OFF - they have never been on, ever. Doing all of these makes no difference to the Newsstand STORE access problem.
Basically, the responses I can see in these 14 pages of people reporting the 'cannot connect' problem over the past 2½ years clearly shows that Apple does not have a clue how to resolve this, or is completely disinterested. This is a disgrace from a company that spends $M per year trying to convince the world that its software is fully joined up and that its service is first rate. Sorry, but the evidence here suggests that in this situation neither is true.
Apple - get it fixed!