>        Allocating colours in X11 is extremely slow in >8bpp. 


Just a wild guess, but have you tried doing ktrace on the Xserver?

It's just barely possible that, rather than dropping in an updated
palette in one syscall, it's doing one syscall for each colour that's
updated, or if it's really simplistic.

I'd have  no trou