Whenever i try adding automatic weights to my model i get that error. i recently had this problem with another model, however that didn't help me with this one. I have tried various things like dissolving vertices in Non Magnifold mode with only boundries ticked. I've removed all doubles and i have no clue anymore. Here's the blend file
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