Hey Lil-James,
This is a known problem with automatic weights also in Blender, which we rely at. Sometimes it simply fails. Two possible causes are known.
The mesh is separated into more than one loose meshpart.
The mesh has a geometry problem like non manifold faces or double vertices.
Seems that you found a third case. I had a look at it, but am also lost what the exact problem here is 
The first thing that i noticed is that you haven’t applied rotation and scale to the mesh, which you should before rigging. Then i went into Edit mode, and performed a Remove Doubles to get rid of possible geometry problems. Bforartists found one double vertice. But this can also be a follow up by applying scale and rotation. I also checked for more than one loose meshpart. All is fine. And so i am lost.
What works is to parent with envelope weights. You have to fix the weighting manually then, bone by bone. You might want to adjust the envelopes before parenting. They are not fitting here and there at the moment …