Vá para o centro de software - > editar - > fontes de software e marque todas as caixas. Eu acho que o que você precisa é multiverso, mas só para ter certeza, habilite todos.
Então, faça sudo apt-get update
(a menos que seja atualizado automaticamente), agora o pacote deve estar localizado.