Bone Heat Weighting: failed to find a solution for one or more bones
Use the decimate modifier, as Shady Puck mentioned.  But instead of Planar, select Un-Subdivide, and use 2 iterations. It looked pretty good to me (~29,000 -> ~14,000 polys).  But make your own judgement after trying that out.

If someone else could tell my why this works, I would be happy.  Even better, please edit this answer, so it actually sounds like a good answer.



After applying that Decimate modifier, I went into your 'rig' (did you mean to use 'metarig' to learn?) and selected the bottom-right four layers.  I had to clear the Pose constraints on the bones because they were all wacky, but once I did that, I selected those bones DEF bones and automatically assigned weights to the VGs, no envelopes required.