Gary Lasker, da Canoical, entrou em contato comigo através do launchpad. Ele me pediu para rodar o Ubuntu Software Center a partir de um terminal usando a linha de comando.
⋯$ software-center
Eu fiz isso e a caixa de pesquisa está de volta. Não houve atualizações no ínterim, então possivelmente foi uma coisa de uma vez (até agora).
Obrigado ao Gary por ter voltado rapidamente para mim!