Another update, because I was still having problems with this, even with all Danpro’s suggestions tried. I found a solution that worked for me, so I wanted to put it here. Apparently Blender runs into problems parenting with automatic weights if the mesh is too dense, that is, in areas where the number of polys increases. I was having particular problems with toenails, for instance. The solution is to increase the size of both the rig and the mesh (I scaled by 10x, because it was an easy number to remember), apply the transforms on both, and then again try to parent with automatic weights. You can then scale back to normal size once you’re finished.
