Ok, I got my Linux box working again. Turns out it was just the main harddisk that was too full!
Fixed it by holding Shift during boot, entering recovery mode and selecting clean.
I really, really, really wish that there would be an error message durinig boot when this happens telling you what happened and how to fix it. Could that really be too hard? I thought I'd lost my data and would have to buy a new PC.