I've recently completed two LED cubes. They're only 4x4x4. Lame compared to the 8x8x8 or even larger cubes out there, but I had a lot of fun building them and I thought this would inspire others to build their own. It was a lot of work, but very rewarding. I don't recommend it as a first Arduino project, but if you've had one or two projects under your belt, you may want to try these. If you've built one, maybe you can post a link/video on this thread.
4x4x4 Single-color LED Cube
More info at my blog
Charlieplexed 4x4x4 RGB LED Cube
More info at my blog