I'm had this same issue even after following all the suggestions in the article Linc posted. That article was helpful, however, because I noticed that in my login keychain there is a certificate (com.apple.idms.appleid.prd....) that has a child key for my Apple ID that is tied to an old email address that used to be tied to my account. (I changed that a while back, but can't remember if I've successfully accessed the app store since then.) There is no matching key for my current login/email address, so I suspect this might have been the problem.
I scoured the web for info on what to do about this but couldn't find anything. This is what I I tried, but I know just enough about certifcates to be dangerous, so I'm not sure if this actually fixed the problem, or if it's a fluke. If anyone knows whether this was a good idea, a really bad one, or unrelated, I'd appreciate the feedback:
1. Exported the parent cert (including the apple id key) as a backup.
2. From context menu on appleid cert, chose "New Identity Preference..." and entered my new email address there.
I'm now able to access the App Store.
TIA,
LSharkey