Likely you might be up against a re-enrollment issue which comes up often for me if they had been suppressed previously and trying to get them back into the active workflow. I found a lot more success building all my workflow criteria into an active list versus in a workflow to manage the re-enrollment a lot better of a specific contact.
On the workflow level do you allow someone to re-enroll when the criteria are met? Also, have you tried doing a test on the workflow level to see if it would allow them in? If not that’s a good sign something is blocking them from getting added in and helps in the process of tracking down what.