Esta coisa de seta para baixo costumava funcionar para mim mais cedo e funciona novamente desde o primeiro beta do KDE 4.9. Então você pode instalar a versão release candidate do KDE 4.9 ou esperar até o lançamento no dia 1 de agosto.
Você deve ter especificado sua distribuição. É possível que este seja um bug somente do Kubuntu.
Então, caso você esteja usando o Kubuntu, apenas a primeira versão beta estará disponível para instalação ( instruções ), como os betas posteriores e candidatos de lançamento foram ignorados de alguma forma ... Mas eu estou usando isso por um mês já e é muito estável.
Mais uma sugestão é usar krunner
(atalho padrão Alt + F2 e você pode alterá-lo). Funciona melhor para pesquisar coisas.