I tried the Time/Date trick without success. Oddly, I can connect to the Search, Updates, Charts (and Categories), and Genius sections of the iTunes Store, but I can only connect to the Featured area sporadically. When I attempt to connect to the iTunes Store via Passbook, I get the "Cannot connect to iTunes Store" message, but now when I dismiss the message, I'm able to connect.
Go to Appstore and logout from your Apple account and log back in, then try the Timetravel to 2013. This is what finally fixed the issue for me.
Link to my blog explaining this