I think I'd start by using a heat map tool like CrazyEgg to find out how people are using your site to see if it's a simple design problem.
If it were mine, I would put the search box near the category list, probably right above it labelled "Find an article" or something similar. Don't bury it off to the side in the upper right where LOGIN is typically done. Right above the category list or site nav on the lft would be my suggestion. Make search very dominant.
If they're complaining on a contact page, put something on that page: "Having trouble finding something? Use our search..."