entityFieldQuery not returning term references - not in field_data but are in field_revision
So, I figured out what was going on -- I was using the 'moderation' plugin and so all the changes I was making were secretly getting marked as 'draft' despite me making the changes as an admin. Doh.