Hello: Can't believe I am joining a two year old post with the exact same problems that people had in 2013 - namely that I was stupid enough to change my AppleID password and then to try to change my iCloud password - but now I can't log into iCloud. Why on earth is there a separate iCloud password? Why is iCloud not a subset of the Apple ID password/account? Why has this not been fixed in the last two years? so anyway, Apple ID changed successfully - but epic fail on iCloud change and now unable to access iCloud services.
I'm currently using iOS 8.4.1. Instructions were given back in 2013 (quoted below) and I'm wondering whether these are still good for 8.4.1:
If you have an old ID (email address) in Settings>iCloud as a result of updating to iOS7, you have to go to Settings>iCloud, tap Delete Account, provide the password for the old ID when prompted to turn off Find My iPhone, then sign back in with the ID you wish to use. If you don't know the password for your old ID, or if it isn't accepted, go to https//appleid.apple.com, click Manage my Apple ID and sign in with your current iCloud ID. Tap edit next to the primary email account, tap Edit, change it back to your old email address and save the change. Then edit the name of the account to change it back to your old email address. You can now use your current password to turn off Find My iPhone on your device, even though it prompts you for the password for your old account ID. Then go to Settings>iCloud, tap Delete Account and choose Delete from My iDevice when prompted (your iCloud data will still be in iCloud). Next, go back to https//appleid.apple.com and change your primary email address and iCloud ID name back to the way it was. Now you can go to Settings>iCloud and sign in with your current iCloud ID and password. (Randers 4).