Hi!
I’ts most likely because the category logic by default respects a rule, where “all categories should match from the selected set” in order to give you a result. In most cases this logic is the best, but you might want to change it.
You can change this logic on the Frontend search settings -> Advanced Panel: http://i.imgur.com/oFG672P.png
