I guess it depends on the interface of the LED-matrix. Is it a serial, SPI type interface with the actual LED-drivers and multiplexer built in or do you intend to drive the actual LEDs with the PIC?
Let's say 8bits per color * 3colors * 256 pixels * 50 frames = 307200 bits per second or 38400 bytes per second.
But why 50 frames per second, I'm quite sure 25 would suffice which would reduce the needed bandwidth to 50% or ~155kbit per second. Then of course the actual bandwidth is twice that since you need to first read the data from external memory then send it out again.

Do you have a link to the display in question.

/Henrik.