I struggled with this issue for a week. Then, Ta Da!
Apple gave great/patient support as we methodically went through each step, escalation to new levels as their knowledgebase dictated. One of the last suggestions was that I disable my McAfee virus protection. No help. They would get back to me...
Upon reinstalling McAfee I ran a scan and found virus infections that were unresolved. Deep breath. Time to clean slate. End of story. iCloud now works like a champ. Just saying, it's worth a check.
Wishing the contacts could sync with my Yahoo. Oh well.
On the phone three hours w Apple. Never did that w Microsoft.