I'm getting exactly the same problem.
Some of my saved searches include a notebook search (e.g. notebook:Timeline). I haven't changed that notebook at all, however now some of them are crossed out and say 'the Notebook for this search has been renamed or moved'. Even though it hasn't.
Searches work totally fine in Windows and Android client.