¿Seguro que has hecho un "apt-get update" antes de querer instalar nada? Prueba a hacerlo y luego instalas lo que quieras.