I contributed earlier that I got fixed by resetting password and deleting accounts on all devices (everything that i got) followed by recreating the accounts.
Support provided me with a fix for the problem that I had.
However as the problem is obviously caused by a corrupted password control server it seems to me that the server problem will take longer to fix and might eventually be fixed by the iCloud people. Don't hold your breath.
In the meantime I offer another suggestion. Support did tell me that my passord may have been invalid, ie did not have the required number of capital letters and numbers.
My password was an old one , used by me on Mobile me and apparently Icloud requires Capital letters and Numbers in it.
Perhaps iCloud is crawling through all the old passwords and invailidating them. Mind you it would have taken took 6 weeks for them to discover my old mobile me passord was invalid.
It would still be a bug if they invalidated it without telling me.
Just another thought. At least I am working well again.....