Are you using categories name to search products? Sorry, but products search does not search categories, only products by title, sku or description.
If you want to get categories search you should either use the separate plugin or made additional customization of existing search.
