I've noticed this too (i.e. "todo:*"). It seems to be that List Item check box is no longer included in this search, only the Insert -> Checkbox items are included.
There is also a similar problem with the "sharedate:*" search term in that it now only returns items shared with a link. Anything shared with a specific email address doesn't show up.
I've opened an incident with the support team, but it's been slow going so far.