The most likely issue here is that all non-deep paints don't work very well with grey coloured blocks. What paints do is change the hue of a block, but if a block has a very low saturation (i.e. is grey-ish), then that hue change will have very little to no effect. However, there do exist Deep Paints that help with exactly this problem, increasing the saturation of a block as well as changing the hue.
What you can try is to craft Deep Green Paint at a Dye Vat, requiring two Green Paints (you can do this with all paints, except Black, Grey, White and Brown). If you apply that to Grey Brick, it should actually turn green. If not, please let me know so we can delve into this issue further.