Blender 2.74 (x64 Linux): Application of Hair Dynamics produces unexpected results
Don't worry! I've found my solution.

Convinced that the problem was due to the mesh, I continued to look into things regarding its construction. Whence, I looked at the scale. The X, Y, and Z scales were all uneven, and more importantly not 1.0.

For reasons best known to Blender, if a shape is not scaled "normally" i.e. 1x1x1, it seems to upset the physics engine in this respect.

The solution was to change all the scales to 1 again and using the scale function (S followed by X, Y, or Z) resize the mesh to fit. Since I had an armature, it was unaffected so I un-parent-ed it and made it fit before reparenting.

The physics engine has been happy since.