Somehow I got duplicate term names in the same vocabulary.
When Feeds tries to map by name, it picks the first matching term name created (lowest TID). But node forms etc use the last matching term name created (highest TID). So there's a mismatch between what's being imported and what users see when editing. The imported data is essentially worthless (mapped to TIDs that are no longer in use.)
I think feeds should pick the latest matching term name. I've attached a patch (my first, hope it works) to make that happen.