I too am having the exact same problem so if there is a solution out there I would be interested to hear about it.

I made my original head model in Maya and am confident of my UV mapping and model so am not sure what the problem could be.

I will go and do some of the suggested fixes that have been mentioned and come back here and let you know how that have gone.

the problem is with your UVs not smoothing and as a result there is not enough space in the UV to catch all the paint properly.

before subdividing, set the options to subdivide UVs and smooth UVs in the small options box next right to the “Add new subdivision level” in the “mesh” menu.

http://www.FX81.com

When i started to learn how to proper uv the models i faced that same problem often. You can have unsmoothed uvs but next time when you have a model with sharp corners, give it more uv space, (by default automatic unwrappers ignore this) It doesn’t matter if you use mudbox or zbrush etc, this will show in those also if you don’t compensate the uvs.