Bone Heat Weigthing failed to find solution for one or more bones
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: