Yeah I'm having this problem too, and I live in Massachusettes. I try to log into the store, and the message "currently undergoing maintenance" appears. I has been three weeks now since this problem has been going on.
NO, deleting the store app then re-installing it does not work, not for everyone.
No. Sometimes you have to make sure your date and time are set correctly too. If you do all of these things it should be fine.
I just had this problem also. What I discovered is that my date and time had somehow switched to the year 2015. When I switched it back to the correct date I was able to access to the store no problem.
Check to make sure your date and time are correct.
My date and time were all correct and my internet is working just fine.
Uh-huh...and did you delete and reinstall the store app too? Press triangle on the store to bring up the options.