Bone Heat Weighting: Failed to find solution for one or more bones?
One of the problems that the automatic algorithm is not good at is dealing with characters maden of spare parts and not an unique closed manifold mesh.

You can separate all spare parts and rig them one by one: it works but you'll have to tweak  the automatic weights manually, because the algorithm doesn't know which part should be moved by which bone.

As your beautiful character is so complex, I would absolutely go with manual weighting, which is less complex than it seems, see this answer for some weighting tips: Rigify : skin overlapping clothes