O Centro de Software nem sempre funciona 100%, tente usar outro programa como synaptic (GUI, mais fácil de usar) ou aptitude (terminal, mas com menus, "semi-gui", CTRL + T abre o menu, então setas ou cliques do mouse podem funcionar), ou as ferramentas de linha de comando como:
apt-cache search "nvidia"
Para mim, uma saída parcial é:
$ apt-cache search "nvidia"
dmraid - Device-Mapper Software RAID support tool
conky-all - highly configurable system monitor (all features enabled)
xserver-xorg-video-nouveau - X.Org X server -- Nouveau display driver
ubuntu-drivers-common - Detect and install additional Ubuntu driver packages
e depois de encontrar alguns pacotes (nome é a primeira parte, antes do " - ") um olhar mais atento com:
apt-cache show <packagename>
E instale com
sudo apt-get install <packagename>
Você alterou algum repositório de software? Isso pode causar erros estranhos às vezes. Esses links podem ser úteis para alterar / redefini-los: