I've not had any recent problem with my iPhone calendar, but I'm using Google Calendar rather than iCloud.

My only issue I ever had with push failing was when I upgraded the iOS on the device. The upgrade replicated all my calendar settings but not the google calendar *password*. So it looked like all the calendar stuff SHOULD have worked when I browsed the settings, but it Just. Wasn't. Working. I never saw an error message saying that the password was failing. Eventually I poked at the menus and settings enough to get the thing to prompt me for the password again, and after entering the password, it's been working flawlessly ever since. But it was odd that it didn't prompt me for the password at first, it just silently failed until I poked hard enough.

I know that's not your issue, but I recount it here in case it might help someone else, or perhaps offer additional insight into why a different calendar might not synch.