Calendar problem. Please help!

So, the calendar on my iPhone won't save new events - it just gives the error message "Cannot Save Event" "That event does not belong to that event store".

Any ideas? I've got iPhone 4 with iOS5. I'm using a me.com account that used to be a mobileme account, and I'm using a GMail address for purchases.

I've now realised that it also won't let me save any new phone contacts. It goes through the process ok, but the contact isn't saved.

Thanks for the suggestions.

I resolved the issue by restoring through iTunes and setting the iPhone up again from backup. I think it was an iCloud related problem even though I'm sure I followed all the upgrade procedure properly. I re-added the iCloud account through the iCloud menu option, not through Mail,Contacts,Calendars.

An odd problem, but now resolved thankfully.

I've opened this thread back up, because after attempting a backup sync to iCloud, I've got the problem back again. No contacts save, error messages come up in calendar.

I will reset the phone as before (long and tedious), but this is an iCloud problem.

I won't bother backing up to iCloud again. Frustrating. "It just works"...