Interesting find @ronan ducluzeau (zeauro). I agree that manually subdividing the cube does not cause the problem until you modify the geometry.
I can also confirm that disabling 'Use Limit Surface' fixes the problem, again until you modify the geometry.
Here is a manually subdivided cube rotated a little.