To search for indexing; always by random search. But you've ruled out that problem.
Well, if a few days without the cover doesn't help, I would call Amazon. And if it helps also call them for a refund for the cover.
Perhaps they will ask to look inside your Kindle (did it with mine), suggest/push the 3.0.3 update, or give you a replacement.
Excuse me for asking the very obvious: you're sure the Kindle is fully charged? Battery-indicator doesn't always tell the truth about it.
Good luck again.