Just wondering if you can only go upto 3x3x3 with a Arduino, as they are the only sizes iv seen running off the ATMEGA168.
LED cubes don't scale well! A 3x3x3 cube is 27 LEDs (obviously), and a 4x4x4 will be 64 LEDs. Remember that current consumption will go up as the cube of the size, unless multiplexing is used. And multiplexing will reduce the brightness of the LEDs, perhaps drastically. Then there are issues like the complexity of the wiring and the cost of the LEDs!
I don't think there's any fundamental reason why you can't make a bigger LED cube with the Arduino, but it seems that 3x3x3 is a reasonable practical size.
Considering a flat 8x8 RGB matrix is 192 LEDs, I'd say you have a little room for more LEDs from an Arduino. But you're going to have to learn how to use shift registers and/or LED drivers to offload some of the bit fiddling and selection. The 74HC595 package is very cheap and seems quite useful in that regard. The Maxim chips are much more expensive but people seem to find a few cheap samples for hobby projects.
Here's a 4x4x4:
http://www.syedrezaali.com/blog/?p=133