I've just upgraded to 5.3.5, and the search works fine on books that are already on the Kindle. I see no reason why it would stop working when I'd load new books.
Hard reset: do you mean a reboot, or a factory reset? If you tried only the reboot, I'd do a factory reset and re-upload your books.
|