When Un-Checked ≠ ‘F’
Symptom: When you create a checkbox on a record and then reference that in your workflow (checking if it is un-checked), note that un-checked could be either null or F. If you haven’t updated that record since creating the box, it defaults to null and your workflow condition that says MY_FIELD = F will not evaluate to true, because F and null are treated differently.
Easy fix: Mass Update all records you just added the checkbox to.