Texture Paint won't paint the whole face - Bleed option seems to be off
Indeed it seems there's been a regression since 2.76. I reported it here https://developer.blender.org/T52453

Meanwhile, here's how the bleeding algorithm works on triangles :



this explains the non parallelism between the UV edge and the bleeding edge 

since the regression, the bleeding treats a quad as 2 triangles.

In any case, most of the times, the best method is to not use bleeding, but paint on a transparent image, export it, import it in the compositor and feed it through an Inpaint node. This gives an even thickness and prevents bleeding in other islands or inside the same island.