Different search results in Adv Search vs Search Builder
After you have made your advanced search and get no results, you will stay on the advanced search page.

If you look at the bottom of that page it will say "No matches found for:" and then list the options you have chosen. Can you see anything in there that wasn't related to the options you picked?

I only mention this as I have a similar problem and I can see that the "Preferred Language" field is being set to Afrikaans, so therefore making any advanced searches yield no results.