I know you posted this almost two years ago, but I've had the same problem and just found a solution, I figure it could help someone! TL:DR press "Set From Faces"Set From Faces in the shadingShading tab of the tool shelfTool Shelf.
What's happened is your normals have got bent out of shape in a weird way that the usual Ctrl-N "make normals consistent"Ctrl + N 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 directiondirection. So you just tell blenderBlender 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.