I may be very, very late to the party but as mentioned this was more than likely due to non-manifold geometry.
In Blender 2.80 I used the advice from an answer that I now cannot find to go to
select>Select all by trait and then clicked all the options until I discovered some of my verts were non-manifold. The closest approximation to the answer lies here (it gives a shortcut for selecting non-manifold geometry instead).
In the end after discovering by tweaking the settings of the aforementioned
select all by trait tool that some verts were non-contiguous I asked stack again for the answer and hey presto!, just recalculate internal normals.
N.B: this is what worked for me, but tools are linked to deal with identifying your non-manifold topology issue in many scenarios