You are not alone.
This needs an Apple iCloud Guru to clarify & solve.
This first showed up for me in Mavericks 10.9.3, and was not fixed in 10.9.4. Neither was a beta version. Updating to a later version of the OS also fails to resolve this suggesting that perhaps it is the iCloud authentication server that is broke -AGAIN!
Unfortunately the Apple helpdesk knows nothing of this issue, or are trying to keep lit under wraps.
My guess is that some of the downloads from Software Update are in fact experimental builds, Noting that is some countries Apple is playing with two factor authentication, perhaps we have been hit by a build that is trying out an alternative authentication method, that simply keeps failing. Though perhaps it is geolocation triggered, as doing a clean install achieves no improvement.
ICloud, which I prefer to call iClod still has bugs, but unfortunately those best able to fault find the authentication system are not available to users, so getting this bug fixed will involve further contributions from more clued up users.
Unfortunately it seems that the failure manifests in several ways, with at least 3 different, but cryptic seemingly random dialogue boxes appearing in response to entered passwords, and also no apparent response at all, i.e., no change.
What is odd is that one can be successfully signed in to iCoud, able to manage ones account, but unable to successfully verify ones password in the preference pane. Looking deeper in the console loads there is reference to a file not being able to be written. So is this a permissions issue, or is the preferences file to be written missing from the bundle from the iCloud bundle.
And even more oddly when one intentionally enters an incorrect password in the password verification dialogue, iCloud seems to correctly identify it as an incorrect password, suggesting that iCloud recognises a correct password but then fails to complete the verification transaction.
Note this iCloud preference pane userID password verification process is not documented anywhere that I have been able to discover. Is it another inadvertent FEATURE of OS X that was mostly deprecated because it did't work as expected?
One day Apple will wake up and instigate a dedicated iCloud help call centre tasked to ensure that all users have access to this service which has become intrinsic to ownership and use of a Mac.