TL:DR press *Set From Faces* in the *Shading* tab of the *Tool Shelf*.

What's happened is your normals have got bent out of shape in a weird way that the usual <kbd>Ctrl</kbd> + <kbd>N</kbd> *make normals consistent* doesn't see as a problem.

They're all facing the right way vis-a-vis inside/outside, but they're all over the place in terms of direction. So you just tell Blender it needs to force all normals to be perpendicular to their corresponding face.

I still have no idea how this problem occurs in the first place, though. It foxed me for a good few days.