I don't recall since which version of Blender but I've noticed that literally all my character models and armatures no longer work with automatic bone weights feature. None. Every single time get this error:
Bone Heat Weighting: failed to find solution for one or more bones
Actually, Blender fails to find solution for any of the bones.
Here's an example blend with a simplified armature and mesh to be parented to the armature ready. Try it yourself: http://www.pasteall.org/blend/42650
Maybe I'm doing something wrong, but Blender didn't complain few versions back. What might be the issue?