Você usou os seguintes comandos no Terminal depois de instalar o Ubuntu recentemente. (Se você não fez isso agora)
sudo apt-get update
sudo apt-get upgrade
depois, pesquise novamente no Ubuntu Software Center. Se você ainda não consegue ver o software, tente isso no Terminal > >
sudo apt-get install gimp