Si c'est un celeron, il te faut un compilateur gcc pour x86. Souvent, son nom complet est i486-linux-gnu-gcc (parfois c'est 386, 586 ou 686 à la place de 486, et parfois il n'y a pas le linux). Ce qui est bizarre, c'est que ce gcc là est le plus courant, donc il devrait être dans tes dépôts (sous le nom gcc).
À ta place, je vérifierai la configuration des dépôts.