>How would you design a query interface friendly enough for this customer?

You could offer two interfaces, and advanced and simple, aka: full logic model and the limited model.

Or make him tell you how many people he knows that were born in CA and TX. Then CA or TX.

Maybe you could offer a little Query Tutorial or help, and make sure to outline logic.

Or, if know records are returnred, before diplaying the (lack of) data, check fir any ANDs in the query. Then tell them no records match and ask if they meant OR instead of AND.