Cookietk's suggestion worked for me too. You probably do NOT need to restore your phone. I went into languages and changed it from English to British English, and then immediately changed back to English.
I went back to the app store, and like someone else stated, the apps I had tried to download acted as though I had "purchased" them, even though I had received the error (it was the download symbol, rather than the inital purchase, even if free.)
A couple other things that I thought might help.. I had actually run into a problem taking one of the more recent iphone updates. It crashed right at the end and forced me to restore my phone and install from backup. When I did so, it was very strange, all the photos and texts came back, but all the app content was missing. When I would redownload something I had already purchased, it would put it back into the folder I had created for it, even if the folder didnt exist on the newly restored backup phone.
I wondered if it was bc i took the update on my laptop instead of my main computer. I tried resynching the phone in the itunes store on my main PC< which acts like it's going to add all thsoe apps back, but it did not. Whatever, I can re download the apps, nbd. Just thought it was worth mentioning.