RaveCraft:
The Arduino can fade any number of LED at the same time. Not using delay(), though. That function absolutely, positively, has to do.
Wait... so why does it work one way but not the other then?
The simplified but not totally accurate explanation is that if you use delay, you can only do one thing at a time, because you can't do anything else while you are waiting for the delay call to complete.