9th May 2016
Another symptom is a message along the lines of
the notebook you are searching in has been moved or renamed since the saved search was created
(which is not true).
I had this problem, and found a solution.
Go to your Evernote on a client where you can edit saved searches (Windows for me),
edit all the searches, and make sure that notebook name is quoted in the search (and also, possibly, with all proper letter cases).
I found this solution by first creating a search from the web-beta interface, it looked like this:
All the crossed-out searches (despite working totally fine on Windows) looked like this:
or even like this (note the lower-case 1st letter of the notebook name):
After editing saved searches and synchronizing, they all appear (and work) just fine in the beta web-interface.
If you cannot edit your searches right now, there is another workaround: all the saved searches work fine for me from the Shortcuts menu (a star in the left panel).
Hope this helps!