This is one of my favorite ideas. My paint game idea is a 2D platformer about using paint to make platforms. Imagine you have a black and white world. In this world the player sees that there is a door. To get to that door a player has to get across a gap that is too large to jump across. There is an invisible platform in the middle of this gap. If the player tries to jump onto this platform he will fall right through it. The reason that it is invisible is because it is "painted" the same color as the background. If the player throws a glob of paint onto the platform it suddenly becomes solid where the paint has landed. The player can then use the painted part of the platform to get to the door. Painting things the opposite color of the background makes them collideable. The opposite is also true. If there is a wall between you and your goal, you can paint a portion of it the same color as the background and then walk right through.
This idea of painting things to change their physical properties can be used in a bunch of different ways. You could paint walls in and out of existence. You could paint "holes" into the floor to gain access to different areas. The if the background was grey, painting something black or white would have no effect on it's physical state. There could be black and white enemies that can be defeated by painting them.