For a long time now Blender 2.5 particles have been crippled in the way that you couldn't animate particle material properties like color with particle age. In Blender 2.4x this was accomplished by creating an ipo-curve to a material property and then by some magic the frame range 0-100 was mapped to the particle life time. For me this always felt very unintuitive and hacky, so when the feature got naturally broken with the animation system update for 2.5 I didn't really feel like reimplementing the feature until a proper way of doing this was found.
To make a short story even shorter yesterday I found the way :) For quite some time textures that were applied to hair strands have had the "strand" coordinate option, which uses the point along a hair strand as the x-coordinate of the texture lookup. I simply upgraded this option to "Strand/Particle", so for normal particles this coordinate option now uses the particle age as the x-coordinate. Simple and extremely powerful! As an additional feature the y-coordinate is mapped to the location of a trail particle, so particle trails can be faded and colored nicely too!
I'll try to make a short introduction video to this functionality in the near future, but for now I hope you have fun playing with this! Some more technical information in the commit message.