uC platforms to consider for faster CPU and 30+ GPIO pins
I would step up to a cheap ARM. You can get the Freedom Board which is a Cortex-M0+ which can run up to 48Mhz. Also being an arm you will get 32 bit registers so you can do more per op-code.  Also it has a DMA engine so you might be able to off load the loading of the LEDs to DMA while the processor updates the memory. You can get them from Digikey as well as the other usual suspects.

As for development tools there is CooCox, mbed and CodeWarrior.