Execute o Ubuntu Software Center a partir de um terminal usando a linha de comando:
software-center
Se ainda assim não funcionar, você deve redimensionar a janela do Ubuntu Software Center e torná-la um pouco maior. Se eu redimensionar minha janela para esse tamanho, a Pesquisa desaparece porque não há espaço para exibição.