It's not possible to say exactly why from your question, because it could be due to ripped edges. However, based on the solution you posted, I can confidently say it is because of autosmooth settings (which you realized.) I can also explain why autosmooth did what it did.
Basically, autosmooth is poorly named. It does not smooth anything. It should be named "autosharp" because what it does is automatically sharpen edges of a smooth-shaded mesh. (It will not do anything to a flat shaded mesh.)
Autosmooth is a technique to automatically mark edges as sharp or smooth on the basis of the angle between the two faces joined by that edge. You'll notice on autosmooth settings that, in the absence of custom normals, there is a number associated it with it, a number that you can change, that defaults to 30 degrees. What that means is that autosmooth is automatically marking as sharp any edges that represent a 30 degree angle or greater. If you change that number to 90, it will mark all edges sharp that represent a 90 degree angle between faces. Like all sharp edges, these edges create split per-corner vertex normals. It is very similar to ripping those edges, perhaps with an edge split modifier: the faces on the other side of the sharp edge will be ignored by the corner-vertices on this side of the sharp edge.
Why would you want to use autosmooth? Let's say you're making a tank. It has sharp edges, but it also has smooth edges-- the turret, the body. By enabling autosmooth and tuning the angle of the edges that get sharpened, you can probably not worry too much about tediously marking this edge sharp, but not that edge. You can just have it calculated on the basis of face angles.
Note that autosmooth is also used on meshes that have custom normals. Custom normals are per-corner in Blender. All vertices have custom normals or no vertices have custom normals, although a particular corner might have custom normals that agree with its default vertex normals. When you have custom normals, autosmooth tells Blender to use your custom normals; otherwise they are ignored. In this case, enabling autosmooth does not sharpen any edges, and you'll see that the angle field is grayed out and uneditable; it is ignored. If you need to disable custom normals in favor of autosmooth's auto-sharpening, you need to discard all of your custom normals (in properties/object data/geometry.)