When using both AND and OR in a query you need to know the operator precedence to get it right. Your query says:
Select something from tables where one of the following two is true:
1. userinfo.category1 is 'female'
2. usernifo.category2 is 'female' and paidstatus is yes and haircolor is brunette...
In other words, everyone that have userinfo.category1 = female will be selected. I think that you mean that the query should be like below
Select something from tables where all of the below are true:
1. either userinfo.category1 is 'female' or userinfo.category2 is 'female'
2. paidstatus is yes and haircolor is brunette...
Use paranthesis to make it so.
By the way, why do you have two category's in the same table? Without knowing more than what you have posted I would say that it is not normalized and that it will get you in trouble, especially with more complicated queries or if you later allow one more category. Instead you should use one table to categories with only userid and category.