Looks great!
I've been scratching my head over the performance change, and I'll probably ask to see your code at some point. But it strikes me that algorithms don't always scale linearly. For example, maybe moving to 64 lights meant that some of your mathematics got pushed from 8-bit math into 16-bit, or 16-bit into 32-bit, etc. Or you crossed a barrier in how much you can get done between timer interrupts, so it has to put what you were doing on the stack and get back to it later.
If I take a look at some of your code I might have a few ideas to streamline some of the processing. The 80 MegaBrite wall we made seemed to update pretty fast, I remember something like 30ms, though I didn't need that much.