How to fix "bone heat weighting: failed to find solution for one or more bones"
If you want the frosting move according to the main body I would recommend the DataTransfer modifier as solution.

Therefore you should parent the frosting to the same armature as the Gingerbread man. But you don't have to make weights just the empty vertex groups.

My example scene looks like this 



So, for Bone deformation we need the Vertexgroup information projected from the Base(your gngerbread man) to the Addon(your frosting).

The modifier has to be on the Addon and it should look like this.



depending to the Size of your object you may change the ray radius

After getting the weight information from the base object you should be able to join the two meshes together(but you don't have to). The frosting should have reasonable weighting. 

EDIT:

After projecting the vertexgroups you have to apply the DataTransfer modifier, because it will automatically recalculate it when you change your pose.

Edit2:

Parent just one object at the same time to the armature.