Actually, you can paint them and they are affected by it, only chances are you're not going to see the difference. To explain why, you need to understand how HSL works. If you already do, just skip the next paragraph.
You are probably aware that colours on a computer screen can be broken down into a red component, a green component and a blue component. This is the RGB value. However, there are more ways to break down a colour, one of them being HSL. This stands for
Hue,
Saturation and
Luminosity. Very basically (and I mean
very), hue indicates whether the colour is red, green, blue, yellow, orange, and so on, saturation indicates to how 'pure' that colour is (a saturation of 0 meaning a shade of grey, a saturation of 100 meaning a very intense shade of your hue), and luminosity refers to how bright a colour is.
Paint changes the hue of a colour. However, as I just said, if your saturation is low enough, you can change the hue as much as you want and it will still look grey. That's why paint doesn't appear to work on grey bricks: their saturation is so low that any hue change isn't going to show.
Enter the
Deep Paints. Deep paints not only change the hue, but they also increase the saturation, so the hue change actually becomes visible. Deep Paints are crafted at a Dye Vat from two of the base paints (so two Red Paint becomes one Deep Red Paint).
Hope this helps!