iPhone says "The Apple Id you entered Couldn't be found or was incorrect. Please try again." All of a sudden my iPhone 4 (iOS4.0.2) can no longer download apps. It says:


  The Apple Id you entered Couldn't be found or was incorrect. Please try again.


I know for certain that the password is entered correctly. I have only 1 iTunes ID. I downloaded an app successfully this morning, over 3G. But now I consistently get this message when I try to download any app! I'm still on 3G with adequate signal strength. 

I've quit all running apps, I've restarted (twice) and even a hard reset. But still I get this message. I've also noticed that the battery level is falling rapidly (1% every 2 min's) despite no other running apps/wifi/Bluetooth, so it must be doing some heavy 3G traffic.

What's up? How can I solve this? Preferably without involving my PC at home because I will be travelling for the next few days...

My exact steps:


tap on App Store
find any (free) app, tap on Install. Itunes closes, I see a white placeholder app icon labeled Waiting..., and I'm asked my iTunes password.
I enter the correct password and tap OK.
The white placeholder icon is still Waiting... for a long time.
After ~5min's the correct app icon is show, but still labeled Waiting.... 
After additionally ~5min's there's a new popup with the text The Apple Id you entered Couldn't be found or was incorrect. Please try again. and buttons Cancel and Retry.


Note: I've seen entries like this one but they are based on working on a Macintosh. I'm at work so I hope for a mobile solution.
This might have been some kind of outage in the App Store, because it works now, following the exact same steps with the exact same conditions (location, network, etc.).