Cant texture paint when zoomed in
If switching to orthographic view fixes it, your issue is that you have too few faces and are too close to them. 

What I do is I add a simple subdivision modifier. It's frustrating that it doesn't work, but blender has trouble localizing the brush on the face when it is severely warped by perspective. Here is a post on the developer manifest.

https://developer.blender.org/T40707