What I meant was, the black boxes are not caused by 8-bit Palleted Texture support being absent in the drivers. It is a separate problem entirely, and at this point, unsolved. (Though it is a graphics driver problem, you are right.)
There is a range of cards (GeForce3-5 ish and some ATI cards) that had the same behavior in FF8Config (failed on 8-bit Palleted Textures) but run the game just fine.
[Edit]
Some digging reveals that on the NVIDIA side, 8-bit palleted textures weren't supported from (at least as far back as) the TNT2 all the way until now, but FF8 works fine on many of those cards. It broke around the GeForce 6. If you have a card older than the GeForce 6, you can play FF8 (but you may need to use older drivers).
For instance, I have a laptop with a GeForce FX 5200 and it works fine on Windows XP with drivers in the 60.xx range, and 8-bit Palleted Textures is definitely listed as "Failed" in FF8Config. (I haven't tried newer drivers, since the manufacturer stopped providing updates around then and the driver's from NVIDIA's site don't support laptop cards.) The behavior was the same back when I had a GeForce 4 Ti4600 in my desktop.