There's quite a few good ideas/references here, especially to some existing approaches. Often, though not always, Apple's approach is a good place to start - but perhaps in your case it may not be. I get the impression (though you haven't actually said it) that you're working with an awful lot of data comprised of many many fields/variables.
I agree that trying to find a way to simplify it for less technical users is a good idea, so long as you expect to have less technical users using the system. Otherwise developing a less complicated interface may be a lot of work for little gain. I also like the idea of a Venn diagram - would be interesting to see how that pans out.
However, in terms of actual suggestions on how to simplify this, another approach would be to just create some sort of "Wizard" process that steps the user through the process with a combination of natural language and a familiar 'web' look and feel. Below is a mockup of how this could work, using an example of a motor vehicle database:

The above shows how Step 1 could work, giving users a number of options they can select by ticking the relevant checkbox. They can select one or more checkboxes as necessary (or maybe not any?!). If they select a checkbox for an option that requires further info then the relevant words are hyperlinked. Clicking on the hyperlinked words would present the user with something like the example below:

So, the example above shows what a user may see if they've selected the "Vehicle is produced by particular manufacturers" checkbox and then clicked on the hyperlinked text to select the manufacturer(s) they want included in the search results. Of course your approach may differ depending on whether they should see a free text field, a drop-down list of options, etc.
Now, to deal with any "exceptions" to the search criteria, you would basically recreate the first window again, but with different wording, like:

So, after selecting the fuel exception above, the user clicks on the hyperlinked words "particular fuel" to choose the exception as below:

Once again, this could be a drop-down list, radio buttons, etc depending on what best suits the condition. They would also go through the same process to select the country they didn't want the vehicle to be manufactured in.
Of course, I see this "Wizard" approach as being for less technical users. You would also offer an "Advanced" option for users comfortable with a more complicated approach that may be streamlined compared to the Wizard approach.
ADDENDUM
Okay, this kept me up last night. I actually see this Wizard approach as being quite a good way to go, so thought it worth coming back to improve on my answer as it may help someone else if not you.
I've updated the mockup images above and wanted to expand on your idea of using a split screen.
Originally I thought that after the last step was complete, then something like your Venn diagram idea could be used to visually indicate what the user has chosen. But then I thought about my original assertion that there should also be a way for the user to go back and forth to amend their criteria. So now I'm thinking that using your split screen you could achieve both. Below is a new image to illustrate what I'm thinking:

So, the above is an example of what could appear in the second part of your split screen. As the user selects their criteria, this updates to indicate what their selections have been. This approach also uses the familiar web look and feel of highlighting their choices with hyperlinks and, if they wanted to, they could change their criteria by clicking on the hyperlinks within this screen, rather than having to go back and forth between screens to redo their steps. Of course, if they wanted to select a new condition, they would need to perhaps go back to the relevant step. But you get the idea.
The only other thing I'd like to mention is that without knowing the complexity of your data, you may need to refine this Wizard approach. My simple vehicle database only needs two steps, but a complicated one may need more steps. The point of this approach though, is not so much in the number of steps, but in the fact that the Wizard 'talks' people through the steps using natural language as much as possible.
Anyway, I hope this, along with the other answers provided, gives you some food for thought. And perhaps some others. This is a good topic and one which I think will be relevant to many users.
Good luck!