Ok so just did a test and it seems that one of the issues with the "Bone Heat Weighting" error is related to closeness of individual verts together when binding. I scaled up the character, rigged him, then scaled back down and it seems to work.  So I guess that was the problem. My character has very thin legs, very very thin, part of an animated style he was made for. So I guess too thin at that scale and the verts were getting too close together in world space.

Only question was, this didnt seem to be an issue if I just left the feet below axis unfixed. This only pops up when doing the fix like 4u2ges mentioned. This is also the method used by Markom3D in his tutorial for rigging CC3 characters with Auto Rig Pro. Which Ive done before but it wasnt working here, so only thing I can think of was the vert distance issue. But still doesnt explain why the character would bind before fixing the feet below axis. 

But for now Im just going to consider it working and not ask questions and hopefully if anyone else has this issue it will help them.