Could always add some external memory via SPI interface to add more, that shouldn't be a limiting factor.
Something like ATMEL AT45DB642D 8Mx8 FLASH would provide plenty of storage.
4-pins for SPI, 3.3V power, gnd, couple of lines to pull high if not being used.
Then yes, the Uno should have no trouble handling this. A 5x8x5 table has 200 elements. If each element is a 16-bit integer (I'm assuming...you didn't say...) that takes 400 bytes. You have 32kbytes of FLASH so there's plenty of space.
Just make sure to use PROGMEM so that this 400 byte table doesn't take up space in RAM:
The Gadget Shield: accelerometer, RGB LED, IR transmit/receive, light sensor, potentiometers, pushbuttons