A. It is not an iPhone 5 issue, because I have it on my 4S and my iPad 2, along with a family member's 4. It is an iOS 6 issue, which they are all running currently.
B. the date fix is not a fix, not only is it ineffective but it is impractical too. Changing the date essentially disables all necessary functions like email, because they can't communicate with the server from the "future"
C. I spoke with an apple representative on the phone last night and he said that many people running ios6 are having this issue, and he referred to it as a "network issue" that should be fixed "within a matter of hours." Unfortunately this conversation took place twelve hours ago so I'm skeptical as to when or how it will be fixed.
I hope that apple has a way of patching it without having to wait for the 6.0.1 update because I'm not trying to wait a matter of weeks before I can search for an app.
I will update with any news about it, such as if the store mystically starts to work again.