I just had this message show up after I added a new calendar on my caldav server.

Apparently, since this new calendar wasn't one of the calendars associated with my caldav account on the N9, the "Data storage full" message was being thrown. This was confirmed by syncing this particular caldav account and having the "Data storage full" message appear.

Once I removed and re-added this caldav account on the N9, the new calendar showed up, and the error message went away. Subsequent syncs no longer caused the error message to appear.

Hope someone finds this helpful.