doh... typed out a reply.... had an idea... went to google it... lost my reply 
my old reply was longer/better.... but you know what it's like... once you loose a reply you don't want to type it all out again
I'm wondering how hard it would be to run 2 arduous, one controlling the top half of the cube the second controlling the bottom half
to keep the cpu overhead to a minimum I'd run them independently, but then have them check in with each other via a couple of digital input output pins - run X number of led refreshes and then put power to pin A and wait for power input on pin B before continuing etc... ( and then cross wire pins A and B between the 2 boards)
each board would still have to run all the maths and keep track of all led's in memory... but it would only have to do half as many IP/OP operations ?
I could add more memory to the boards (that's what I was just googling) - pre-process what the board needs to do, and then have it output everything from memory.... there'd be a short pause every time what was being displayed changed... but it shouldn't be too long... but I'm assuming any add-on ram would be too slow to access via the normal ip/op pins
(I couldn't find anything with a quick google, but I'm assuming reading over lan would be too slow too)
but... I guess it wouldn't have to update/download the next led with each flash of an led...
it might be better to load the status of each led into memory, run through flashing those and then just update 1 of them with each refresh ? (or each 2nd refresh if it needs to run slower etc. etc.)
if something more complicated was slowing it down, the led's would still multiplex just as quick, the only difference being the image wouldn't update/change as often ?
that's all dependant on getting the multiplexing running fast enough of course....
anymore input/ideas are more than welcome.... much easier to do this right first time than try to change it later on !