Did you try disabling Java or just updating it? Have you disabled Javascript?
I had a similar problem problem a few weeks ago; a dialog box would pop up saying the default search provider was corrupt.
First try reinstalling the search providers. Delete the HKEY_CURRENT_USER\Software\Microsoft\Internet Explorer\SearchScopes and HKEY_LOCAL_MACHINE\[same path] keys. Export them first, just in case, but the next time you start IE it will reinstall the Bing search scope (maybe Google too; I can't remember). You may be able to install and set the others after this.
That didn't solve my problem, but this did:
Go to HKEY_CURRENT_USER\Software\Microsoft\Windows\Current Version\Explorer\User Shell Folders. If there's an item called "AppData", change its value to "%USERPROFILE%\Application Data". If it doesn't exist, create a new "Expandable String Value" and give it the same value.