Like i said in my initial reply, I think you may want to use the edit criteria type for the checkboxes instead of the checkbox criteria type.
the difference between them is that with an edit criteria type, the column will not be included in the search if the box is not checked.
with checkbox criteria type, that column will still be included in the search, just using the unchecked value "0"