I think it's something specifically related to the Google Calendar and CalDAV. With my Google Calendar already synced to my N9 using the regular method that syncs your main calendar plus sub-calendars you've selected (just put in www.google.com as the sync URL and use this tool to select which calendars to sync), I tried changing the calendars set in Google Calendar using that same selection tool and then updating the sync in the N9. I got a very similar error message: "Data storage full. Free up some space first." I then immediately tried removing my Google Calendar from CalDAV in the N9, re-adding it, and syncing (with no reboot or anything), and it worked and I saw all my calendars.

There seems to be some bug in the protocol that the N9 uses in PR 1.2 to sync with CalDAV that throws this error when trying to sync specific calendars in Google Calendar, or when updating your calendar sync after adding/removing calendars on the Google side using the iPhone tool. I bet anyone can repeat these out of memory errors by following these steps with PR 1.2.