That's not quite true.
As long as you have the latest BIOS update for that board (and you should be able to find one on the Gateway website), it should handle a Celeron.
The reason that they give 333MHz as the highest is because the Pentium II on the 66MHz FSB only goes up to 333MHz, and requires mutliplier settings.
The Celeron does not need multiplier settings, so it should work, so long as you have the latest BIOS.