Well, for most cases 255 colors do fine. The palette just has to be created carefully. Zoot I assume simply does not reduce colors at all when it encounters more than 255, but you can easily do so in external programs.
It would need much more than a hack. The game rendering engine would need to be rewritten in such a way that supports more colors, which luckily falls under the scope of what we're planning for OpenZT. I don't know how far we'll take color support though. At least I'd like the alpha channel to be supported. That alone should solve many of the 'too many colors' errors.