The Paint tool requires a valid surface to work. Please, be sure you have a surface assigned, it is correct (not flipped normals and so), and you are painting inside the surface's limits.
If this is not the cause, please try to reproduce the problem in a basic test scene, and send it to us.