I know 2 situations where this problem raises:
- When the Object consists of 2 or more separated (not connected) meshes which intersect. This could be solved by fixing the mesh topology, like connecting the intersecting meshes into one single mesh and by fixing your model to avoid the intersecting areas.
- When the object has duplicate vertices. This can be solved by removing doubles in Edit Mode ( keyboard shortcut "W" -> Remove Doubles)
I do not know the exact reason why the algorithm fails in these cases and if there are other cases as well where it fails. However it must be related to ambiguities while calculating the weight ratios for the involved vertices.
I took a quick look into the blend file that was provided by the OP. I found the head of the character has many duplicate vertices (about 320). Removing doubles solved the issue in this particular case.