The iPhone maintains two separate Apple IDs: one for iCloud, and one for the iTunes Store. These may or may not be the same, and they are set in two separate places.
To view and set the Store account, open Settings and scroll down to Store. Beneath the settings for Automatic Downloads, it should show the Apple ID you're currently using on the phone for the Store, e.g.:
Apple ID: pito@mac.com
Tap that, and a dialog will pop up offering three options: View Apple ID, Sign Out, and iForgot (the last is for retrieving a forgotten password).
If the Apple ID displayed there is not what you expect, select Sign Out, and you will be able to sign into the Store with a different Apple ID. Note that this will not affect your iCloud settings, which are managed separately through Settings > iCloud.
Give this a try, and if you are still having troubles, feel free to update your question.
Further note: it sounds like you have inadvertently set up a new Apple ID instead of using an existing one. To identify which Apple IDs are associated with your account, check out My Apple ID. The Manage Your Account and "Not sure if you have an ID? Find out" links should help you get a handle on the situation.
Update: Regarding your comment about the App Stores, there's definitely confusion to be had here: The "App Store" on iOS is part of the iTunes Store - it's the same content that you see when you open iTunes, go to the Store, and browse to Apps, and it uses the same iTunes Account. The Mac App Store, accessed by clicking the App Store icon in your Dock (or under the Apple menu) in OS X is a separate content store containing only OS X apps. That said, it also authenticates using an iTunes Store account, typically the same one you'll use in iTunes.
As of today, the easiest way I've found to think about this - and the way I've configured my own accounts - is:
An Apple ID for buying things, which you'll use to authenticate in:
- The iTunes Store
- The App Store on iOS
- The Mac App Store on OS X
And one for syncing things, which you'll use to authenticate in:
- The iCloud settings on iOS
- The iCloud preference pane on OS X
- The iCloud website
The thing to note about the above is that you can use the same Apple ID for both sets of tasks, but, depending on what you want to accomplish, knowing where to enter each ID is important.
Best Answer
If the servers are broken or the network isn't working between you and the servers, your password isn't actually wrong. Even when all lights are green at http://www.apple.com/support/systemstatus/ it could be an issue that'e exclusively server side, and you'll need Apple Support to get to that conclusion.
Barring that, you can certainly to go through "the usual troubleshooting steps" on iOS since you're unlikely continuing to type the password incorrectly.
You should start with the support article below:
Before you contact support (the link at the bottom of the page - the next step if that doesn't work) is to maybe try a restart. Since the app store needs an accurate time and date: