256 steps are alright for color mixing and for big fades but quite often I'll have the lights down to number 3. They are very dim but they can't really fade out with just 3 steps and it looks a bit odd.
Processing power isn't much of a problem. I use PIC24FJ64GA004 chips to control them which are 16-bit anyway and have plenty of RAM/cycles.

I've got another one of these that can read 8 x 16-bit 44.1KHz WAV files from an SD card at the same time, mix them with 8-bit volume control and output to 4 x 16-bit DACs.
The lighting controller has 36 outputs (12 x RGB) but the refresh rate is much lower.

Thanks for the LDP1886 suggestion 12-bit would still give me 24 steps instead of 3. I'll have a read up on them.