When I bought paint from the painter I tried to paint wood, stone, dirt, and multiple other blocks with paintbrush. Why isn't paint working? Does it only work on certain blocks or items?
You can't paint some blocks with standard paint (eg. Gray brick, Glass blocks...), if you apply the paint of these blocks, nothing will happen even though the paint will be removed from your inventory.
To paint them you'll have to use their Deep version which you can acquire by combining two standard paint at the Dye Vat that you can buy from the Dye Trader for 5 gold.
For example, if you want to paint a Gray Brick in red, you'll have to buy two Red Paint and craft them into one Deep Red Paint at the Dye Vat.
You can paint almost all blocks in Terraria, even trees or furnitures. Just give it a try with standard paint and deep paint! And remember to use the Paint Roller to paint walls and the Paintbrush to paint blocks.