Definitely adding the choices of "AND" and "OR" will not cause you to many problems. Most users are familiar enough with boolean logic to get by.

Adding parenthesis to allow nesting and grouping is something altogether different. Most users can't handle it (heck, even programmers get confused by this sometimes).

The answer is to make this modular. Since users can save these selection criterias, can you make it so they can combine them? That would be a lot easier conceptually.

For example

State = 'NJ' and profit > 1000 can be saved as "NJ - over 1000 profit". Then, if the user wants something more complex they could use:

"NJ - over 1000 profit" AND Gender = 'M'

Then, if they wish, they could save that as "NJ - over 1000 profit - Males only" and use it in even more complex expressions.

A recursive, object oriented model is a lot easier for users than ")" and "(".

PS: I think this is what rdfozz was saying, but I'll post this anyway.