Try to install the hotfix.
Download the "K5 Jailbreak Hotfix" from
here.
Place it in the root of your kindle storage and navigate to settings and try to update.
Also, what happens when you type
into the search bar and press enter? (Make sure you type it exactly as it is. Including the semicolon.)