How do I change the color of a brick?
I don't think that spray paint would be very durable.  Even if you used a primer specifically designed for plastic the paint would scratch off fairly easily.  Also, spray paint would add a noticeable amount of thickness to the brick and could interfere when trying to mate the brick up with others.