I think the fact is that although predicate logic is a foundation of mathematics, it is not what mathematicians spend the majority of their time thinking deeply about. You might use English every day of your life, but still struggle to explain what a transitive verb is, or a gerund.

It would be interesting to run this experiment on CS or EE students. I hope they would do a little better…

All people would do better if they are warned first it's a tricky question.

Also, training in this kind of problems will help.

Not necessarily more troubling than being tricked by an optical illusion. Perhaps this problem is more like a logical illusion because of the presentation/wording.

I think you are presuming that the participants who failed were unable to solve the underlying logic problem, when it is entirely possible that they (eg) misread part of the problem setup.

(Likewise the paper seems to infer a difference in logical thinking rather than considering a difference in processing/interpreting the problem.)

Maybe, but understanding a problem is half its solution. Misread and couldn’t solve correctly are the same thing in problem solving.