O Ubuntu 12.04 não tem todos os repositórios ativados por padrão. Você pode abrir Fontes de Software ou Synaptic e ir para Configurações - Repositórios - Outro Software. Ativar / verificar 'Canonical Partners' e os repositórios 'Independent' e recarregar sua lista de fontes de software. Você pode tentar usar o Centro de Software depois disso.
Por falar em Software Center, nunca uso, prefiro usar o Synaptic e a janela do terminal. Dessa forma, eu sei com certeza se o software que eu instalar funcionará ou não no meu sistema. Eu uso o campo de pesquisa no Centro de Software às vezes para aprender mais sobre novos softwares, mas geralmente eu instalo o software via Synaptic.