Controlling 500 LEDs with PWM
I am the author of the ShiftPWM library and I just updated the documentation to include schematics and a lot more general info for normal LED's, LED strips and high power LED's.

You probably already started your project, but since this page gets a lot of visitors, I'd still like to provide a detailed answer. 

If you want to control 500 LED's with ShiftPWM, you can get about 64 brightness levels per LED at 60 Hz. You would use 64 shift registers. Dedicated hardware PWM drivers will give you more brightness levels, but will be a bit more expensive. I think the main advantage of my library is ease of use, because it includes RGB and HSV functions and a lot of examples.

I would personally go for the TLC5916 of TLC5917 instead of normal shift registers, because they have a built in constant current LED driver. This will save you a lot of soldering, because you don't need resistors.

On my website ( http://www.elcojacobs.com/shiftpwm ) I have more info on how to connect the LED's and how to deal with driving the long signal wires with the Arduino at high speeds.

If you have any more questions, please ask.