When I go to the newsstand on my iPhone 4s to search for titles of magazines it takes me to the appstore, with no offerings of magazines such as GQ, Golf Digest, etc.
If you go into the app store directly and look in the Newsstand option, then you should be able to find a lot more magazines and newspapers, rather then going to the store directly from Newsstand. I have an iTouch and i still have access to hundreds of titles.