My boyfriend had the exact same problem. We tried out everything for days but nothing seemed to be working. Then, in a far off corner of the web I found somebody having the same problem and a fix that worked for us:
I installed an application called "BusyCal" (Google it, there is a 30 days test period offered). Make sure to turn off calenders in the Settings > iCloud before doing anything. I synced it with iCloud calenders and got the same problem but without the popup error message. I tried to delete all of the calenders, didn't help (they reappeared). I gotta say that we downloaded all of his calenders before messing with them on the servers so data would be save. I then found out there were also some Reminder Lists connected to his Calenders (Apple seems to put Reminders and Calenders in one Category). Anyways: these were old and already deleted on his computer but seemed to be stuck in the cloud. I went to iCloud.com and deleted all of them, but one of them kept coming back. So I deleted everything on that list, EVEN the tasks that had been ticked off! Finally that was the fix. That one item got stuck somewhere. So then I basically could delete the list that was left and delete everything else (in iCloud.com). Then restarted, reconnected his iCloud account to calenders and reuploaded the previous saved calenders. Worked!
I hope I could help!
