OK, I figured this out. So if anyone else runs into this, here's the deal...
When you create a new user profile field and pick a default value for it, the individual user profiles appear to include the new data, but this is misleading. The actual record in mdl_user_info_data is not added until you either manually type in the field, or it's updated from an external source. So any cohort rules you add won't be able to find the data.
I thought I had a handle on this last week - when I saw the cohort didn't update, I included records for whom the field was undefined. However, this exposes what I can only think is a bug... when you include undefined, it adds all users, including ones with the deleted flag set. Not a good sign when your cohort has more people than there are accounts. Since the deleted users aren't presented in the UI, I needed to drop back to a backup to get rid of them.