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.
According to Auto Body Repair by Duffy and Sharff, the best solution for any interior or exterior (non-flexible) ABS (acrylonitrile butadiene styrene, the plastic LEGO elements are made of) component is to apply a standard lacquer based system, no primer.
It's Lego blasphemy to change the color of the bricks (or to modify them using, say, a dremmel) but that said I would use the spray paint that is made for plastic. Of course, whenever I go to Lowes the color selection is limited so you may not find the color you need.
Hm, maybe try using British Paints Spray Paint. I think they are the best brand. Just make SURE that it is the exact same colour with the other ones you are using. Spray at about 35-40cm distance from the block. I tried it and it works well.