O pacote ainda está no repositório . Portanto, deve haver algo errado com sua instalação.
Você tem pacotes 'universo' ativados? Você pode verificar indo para
Edit ⇒ Software sources ⇒ Ubuntu software
e procurando por uma linha com universe
.
Depois, você precisará recarregar as informações do repositório (por exemplo, com apt-get update
).