For those who changed their Apple ID and couldn't log out of their iCloud account on their Macbook because it was stuck on the old Apple ID, I have found your solution! I could not figure this out for the longest time until I came across a couple articles that said how to fix it. You actually have to go back and change your Apple ID to the old one (the one your Macbook is stuck on) and then sign out that way. Once you change it back, your iCloud will reconize your password. After you sign out of iCloud on your Macbook, go back and change your old Apple ID to your new one. Then go sign into iCloud on your Macbook.
Summary of steps:
1. Go to https://appleid.apple.com/ and sign in with your new ID and password
2. Change your ID back to the old ID (the one your Macbook is stuck on) HELP: it will not accept any email address for an ID that you already have listed as a back up email address. You will also need to verify these changes in the corresponding email account.
3. Go to your iCloud account in System Preferences of your Macbook and sign out (click to save all of your stuff that it prompts, it will delete thing initially but once you sign in again later it should all come back)
4. Once you are signed out of your iCloud, go back to your Apple ID web page and change your Apple ID again. Change it back to the new one that you wanted before this mishap
5. Once you have changed your Apple ID back to your new one, go back into iCloud in System Preferences of your Macbook and log in using your new Apple ID
*If you do this correctly it will work! I could not get my password to work because it was stuck on my old ID. I really thought I was going to either have it stuck this way forever or have to take my laptop in somewhere so someone could fix it for me. If you follow these steps, you should be able to fix it yourself and still have all of your information.
References:
If you're asked for the password to your previous Apple ID in iCloud - Apple Support I used this idea for ISO and applied it to my Macbook
http://osxdaily.com/2010/08/10/forgot-mac-password-how-to-reset-mac-password/ I had my System password linked with my iCloud which also caused problems, so if you cannot sign into your System account, this also may help you!
Best of luck and I hope I can at least help one other person who had the same problem as me!