apt-cache search não usa um mecanismo de pesquisa de texto completo como o Synaptic, mas simplesmente imprime todos os pacotes onde suas palavras de busca ocorrem no nome ou na descrição do pacote.
Como nem o nome do pacote nem a descrição de software-center contém a palavra ubuntu-software-center , uma pesquisa usando apt-cache nunca será assim.
No entanto, você pode usar várias palavras de pesquisa com apt-cache search e ele mostrará apenas os pacotes que contêm todos eles. Então você pode usar, por exemplo,
apt-cache search ubuntu software center
que lhe dá uma pequena lista de pacotes incluindo software-center .
BTW, o apt-cache interpreta as palavras de pesquisa como expressões regulares .