- Power off and then back on the router
- Reset network settings: Settings>General>Reset>Reset Network Settings
- Try when connected to another network
Try this article: http://support.apple.com/kb/TS1368
Also, if that doesn't work, try this:
First you need to create another App Store iTunes account with a different country. (If you're American, do Canadian and vice versa)
When you sign out then sign in under the new account, it will say that your account only works in USA and to change the store. Once it does that your top 25 will be changed back to top apps and you'll get no more errors. Then you can change back to your normal account.
You can create another account free. Do it through iTunes on your computer or Mac. Change the country at the bottom of the App Store. Try and download a Free app. That way you don't need a credit card.