O Internet Explorer 8 possui uma pesquena falha, ele só possíbilita adicionar o provedor de pesquisa em EN. Pesquisando encontrei uma solução:

Entre na pagina: http://www.microsoft.com/windows/ie/searchguide/pt-br/default.mspx Na pesquisa, clique em “Adicionar mecanismos de busca ao Internet Explorer”, e na próxima página é so escolher o provedor desejado, clique em “Substituir”.

Pronto, o provedor de pesquisa foi trocado.