Talvez você tenha apenas o repositório principal ativado. Abra o Dash (tecla Windows), digite Preferências, abra-as, procure por Software. Na primeira aba você pode habilitar o software Ubuntu (repositório principal, universo, multiverso). Existem também outros repositórios, por exemplo, o playdeb. O Playdeb oferece alguns bons jogos, que não estão incluídos nos repositórios do Ubuntu.
Se você tem todos os repositórios do Ubuntu habilitados, talvez seja apenas um problema de ortografia. Tente usar o nome em inglês do software, com e sem letras maiúsculas no começo.