Probably the source of the problem is the gigantic amount of UV islands created by the “Smart” UV Project unwrapping method that is certainly doing troubles for the Blender painting tools, despite it should not (as i don’t remember seeing similar problem with Sculptris that use something like “smart” uv project too for the sculpt painting)
I think you may report your problem to the bug tracker, so the devs have something to reproduce the problem.
Meanwhile, try a more classic unwrap, with marking seams and etc… tough with this kind of mesh it will be hell even if helping yourself with Select -> Shortest Path between vertices (you should retopo, would be much much easier to work with after that) , on a more classic (as in not hundred/thousand of UV islands), i’m sure the painting tools should work better .