I fixed the problem.
I had two levels of categories: Women/Men, and then subcategories under each of those (in addition to Root). I had listed the product in both the appropriate sub-category (e.g. T-shirts) as well as the parent category (e.g. Women).
After I unticked either Women or Men in the dashboard, meaning that each product has only one category, i.e. the most detailed sub-category, the product API returns the correct data.