Tente isto primeiro:
- Clique com o botão direito do mouse no botão "Menu Iniciar" e vá para Propriedades.
- Vá para a guia do menu Iniciar
- Clique em Personalizar
- Desça até o final e certifique-se de que "Programas de Pesquisa e Painel de Controle" esteja selecionado.
Se isso não funcionar, você pode precisar de um Hotfix da Barra de Pesquisa do Widows 7.