I extruded something from this Obj model and the shading looks segmented as if there were distinct models.
I have already checked that my normals are not inside out.
Normals look ok:
It'd help if you could post your blend file, but what I suspect from looking at the images is that you have duplicate verts or faces. See if you have faces inside that shape, or select all of the vertices and use Mesh -> Vertices -> Remove Doubles.