1,000 LED Control

I wasn't saying I expected 60 fps and 64 shades, I was saying those were my ideals. I expect/plan to get worse performance (that is, lower frame rate and shade count) if I use an arduino.

Did the math to show you what can be done with Arduino

why you mentioned bytes and bit stuffing where you did

64 shades of grey use 6 bit so from every byte two bits are unused. That means I can "stuff" the info for 4 LEDS (4*6=24bits ) in 3 bytes.
This technique is used in base64 encoding/decoding.

that will be very difficult for Arduino to handle (read not)

In theory the Arduino could be able to handle it, in practice I expect it will be too much as there is little time left to process the incoming data in time. I expect that low level assembly is needed to handle the level of dataflow mentioned.

Also not sure how you got 600,000 bps instead of 360,000, or 75,000 instead of 60,000.

To send one byte over a serial line the Arduino uses on average 10 - 11 bits (measured in time), it uses a bit to signal start of the transmission, then 8 bits for the byte and then 1-2 bits (in terms of time) until the next byte comes in. As a rule of thumb one can say to send 1 byte over serial one uses 10 bits. Better use 11 (or even 12) if you want a defensive estimate as serial communication is asynchronouos so you never know when thenext byte will come ...

Where would this bit stuffing come in?

See above, but bear in mind that bitstuffing takes time and the unstuffing of the bits should cost you less time than sending one byte. If it takes more time to decompress datat than to send extra data compression makes no sense. Only a good experiment will give you indications how for your specific project compression vs speed will behave.

Why does the baud have to be so much higher than the bit rate for a simple multiplexer

The reason to use a higher baudrate gives you time to process the data. if you need to transport 75000 bytes per second and you use 75000baud you will have no time left for doing something with the data (assuming a 100% usage of the bandwidth !!). The Arduino needs some time to do the math to switch the right LED.
To get some feeling,

  • write a sketch to measure how much time it takes to send 115200 bytes at 115200 baud. In theory 10 seconds (with start stop etc bits)
  • write a sketch to measure how much time it takes to switch a LED on/OFF 10000 times.

Also bear in mind that 1000 bytes of frame data will take almost half the RAM on a atmega328p. You won't have enough RAM to display the current frame

I think you IF you can shiftOut the current frame into shift registers like the 74HC595 - http://www.arduino.cc/en/Tutorial/ShiftOut - fast enough you could reuse the 1000 bytes for receiving the new frame as the shiftregisters work as "memory" of the current frame. That would be a project in itself to test the feasability of this...

Could you explain?

See above, hopes it is more clear now.
Advice: please spend some time on the tutorial section and the reference section of the Arduino site as you will learn there a lot of the possibilities and constrains of the Arduino and its language.

Succes!