EVERYTHING is working now!
My Problem: After upgrading to El Captain, I just couldn't login to iCloud - no AppStore, iMessage, Notes etc. I kept getting "invalid password" messages on triple checked passwords, some other times it would say "An error occurred during authentication. Try Again." basically random behaviour in general. Also it's not like I couldn't log in to my iCloud account, in fact couldn't log in to any iCloud account. I have a 13inch Macbook Pro, though I'm sure now that this doesn't really have anything to do with my hardware model in particular.
I spent a couple of hours around these forums and consolidated all solutions that seemed to have worked at least once for at least one person. Here is every thing I tried:
0. Changed date/time preferences to update automatically:Nothing changed.
1. Removing files in iCloud/Accounts folder and rebooting : There weren't any, so removed the folder and rebooted. Nothing changed.
2. Cleared the NVRAM (press Cmd+Alt+P+R) wait for two dong sounds during reboot: Nothing changed.
3. Deleted all login keychain entries corresponding to my appleId: Nothing changed
4. Re-installed OSX from OSX recovery : Nothing changed. (ref: How to reinstall OS X on your Mac - Apple Support)
I was just getting ready for a (gasp) CleanInstall. When I decided to try this:
5. Create a new Admin Account, set it to use a separate password, after that account was created I tried to login to my iCloud Account from there. Nothing changed, got the same error I was getting from my user account.
6. Create a new Admin Account, set it to use an iCloud Password, (note: it said that I couldn't use my original apple Id as it was already associated with an account on my Mac, so created one on icloud.com) did the necessary steps for setting up that account, then switched back to my user, and tried to sign in to cloud again, and it worked! It Actually worked!
iMessage, App Store, XCode all signed in and running smoothly!