After attempting to try various workarounds, I manually saved out any credentials I had in the iCloud keychain and disabled it on all active devices. I then created a new one on an iOS device and that was OK, but I tried to add that new one to my Yosemite Mac and received the same message. I cannot even create a new one on the Yosemite Mac.
There are a lot of errors in the system console along these lines:
Oct 31 09:59:29 SYSTEMNAME.local secd[338]: securityd_xpc_dictionary_handler CloudKeychainPro[740] EnsurePeerRegistration The operation couldn’t be completed. (Mach error -536870160 - Kern return error)
Oct 31 09:59:29 SYSTEMNAME.local CloudKeychainProxy[740]: __45-[UbiqitousKVSProxy doEnsurePeerRegistration]_block_invoke <U-K--epC---> ensurePeerRegistration called, failure (The operation couldn’t be completed. (Mach error -536870160 - Remote error : The operation couldn‚Äôt be completed. (Mach error -536870160 - Kern return error)))
Oct 31 09:59:29 SYSTEMNAME.local CloudKeychainProxy[740]: __45-[UbiqitousKVSProxy doEnsurePeerRegistration]_block_invoke_2 <U-K--epC---> ensurePeerRegistration failed: The operation couldn’t be completed. (Mach error -536870160 - Remote error : The operation couldn‚Äôt be completed. (Mach error -536870160 - Kern return error))