Bone Heat Weigthing failed to find solution for one or more bones I am trying to do automatic weighting on this object, but I am getting a "Automatic Heat Weighting: Failed to find a solution for one or more bones".

I have tried alot of different thing

Removing doubles
Removing all modifiers
Subsurface
Decimate
Removing Non Mainfold Vertices

Here is my .blend file:
To solve this:


I first removed doubles. This is caused because of non-manifold
geometry in your model as shown in here.
I then switched into Edit Mode
Then hit Ctrl+AltShift+M to find non manifold geometry in the model
I then unchecked all the list except the Boundaries as shown below:





I then hit Space Bar and type Dissolve Vertices as shown below:





After that I did automatic weighting and it worked perfect as shown below:






Updated .blend file can be found here: