This is a really annoying glitch. I finally got Apple on the phone and got to the bottom of it. Apparently when you change your Apple ID without first signing out of the old one, it remains attached to your account. When you type in the password, however, it will say it's wrong. The obvious solution would be to delete the iCloud account from your phone, but you can't do this without the password if you have find my iPhone turned on. The solution is to go to Appleid.apple.com and delete the old one, the switch the new one back to the old one, then it will recognize the password and you can remove it from your phone. The AppleCare lady said they get A LOT of these calls every day. Very stupid, and Apple is even aware now. They obviously simply shouldn't let you change your Apple ID without first signing out, problem solved.