"type=post" did absolutely nothing, and when I checked the wp_list_categories page in the codex, it wasn't listed as one of the possible paramters, so I'm kind of confused about it.
But I tried deleting the hide_empty parameter, just to see what would happen. I thought it would behave as I described above, but it didn't - all my post categories are showing up, even the empty parent ones and all their children. Which is very, very weird - the fact that empty parent cats wouldn't show up (even if their child cats weren't empty) prior to 2.1 was the reason I had it set to hide_empty=0 in the first place. In terms of template tag behaviour, the jump between 2.0 and 2.1 has been bigger than between 1.5 and 2.0, which is unexpected.
Anyway, thanks for your help!