Could my app store password stop working due to iCloud confusion?
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.