Like so many others, after updating to OS6 and changing my iCloud password, none of my devices (iPhone, iPad, MacBook Pro, iMac etc) could connect to the tunes store, the error message was something "iTunes could not connect to the iTunes Store. Make sure your network connection is active and try again." However, there was nothing wrong with my internet connection - programs like Safari & Mail worked just fine.
After trawling through the discussions and trying the recommendations (change time/date, activate location services, reset network settings etc) I just became more frustrated.
I figured that if iTunes thought my network connection was the problem, maybe I should try tricking it and, after much trial, error and frustration, I did find a solution - and it may work for you...
I turned off WiFi on my iPhone, then connected to my telco's 3G network, then connected to the iTunes store and it worked fine. Then I switched back to WiFi and all is good. Did the same for the iPad. For the MacBook and iMac I turned off WiFi then tethered the iPhone on the 3G network to the computer, then connected to iTunes Store, then went back to WiFi. For some reason that I don't understand, this all went as planned and now everything works.
Anyway, I thought I should contribute to the community by letting you know the solution I found. Of course, this may not necessarily work for you, but it's worth a shot.