Just to add one more data point for this thread...

It seems that a new Birthdays calendar has been added to Google accounts that I've added on Android 5.x devices, e.g. I have a Nexus 10 tablet running Android 5.0.1, and as soon as I added one of my corporate Google accounts to that device, my N9 CalDav sync for that account started blowing up with the usual 'storage space full' complaint.

I just removed that CalDav account from the N9 (and N950, because I'm fortunate to also have one of those), and added the account again, and sure enough... that account has a new Birthdays calendar that wasn't there before I also added that account to my Nexus 10 tablet this afternoon.

I think this correlation has already been made, but the general point is that you'll get the 'data storage full' error whenever there's a difference between the calendars that exist on your N9/N950 CalDav accounts vs what's on the server.