Bone heat weighting: failed to find solution for one or more bones
I also faced this message, the reason was that the model wasn't symmetric (after twiddling with an already applied mirror modifier). In this case you could try to cut off one half and mirror it again. After that the parenting with automatic weights should work.

See also this thread on BA Bone-heat-weighting-failed-to-find-solution-for-one-or-more-bones