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 ).