Found out that the route cause was the log files getting out of control. Of my 2GB storage, about 1.7GB were taken up with logs.
Using the terminal emulator on the phone you can see the directory sizes:
su
cd /data
du -Hd 1
and then delete the logs:
rm -r log
And do the same for these logs:
/sdcard/logs
Thanks to everyone at CyanogenMod, especially WuUWDfxgBtavJy
http://forum.cyanogenmod.org/topic/75054-insufficient-storage-available/