Changing Materials On Multiple Copies Of Same Object (within cycles)
You can use the Random output of the object info node to get random values between 1 and 0 that are unique to each object with the material. You can use this to change the color of an object using a color ramp node:



However, this only works for objects (you convert your particle system to objects with CtrlA> Make Duplicates Real, but they will no longer be animated).

You can kind of do the same thing for particles with the index output of the Particle info node (dividing it by the number of particles), however the output will not be random; the first particle will have a value of 0 and the last will have a value of 1.

If your particles move around and get mixed up enough, it may not be noticeable, especially if you chop up the color ramp node: