I would have to agree that you are looking at this as a power user, rather than a regular user. And, from that perspective, I would agree that the changes are rather minimal and intuitive between recent versions.
However, for older folks, this view is not typically the norm.
I do computer repair and routinely listen to gripes about changes in Vista/7.
For instance, I often hear complaints about things like changing the theme/style settings, searching, modifying network interfaces/settings, or changes to how the control panel works.
These are often, aside from theme/network settings, an improvement, minimal, and intuitive changes IMHO.
But, to someone who is barely computer literate, even "little" things like that can represent a big change and can be very confusing.
And, of course, the change from Win7 et all -> Win8 is massive, even to me...
I don't think that these changes actually require re-learning the OS, though. They do require some learning, but "re-learning the OS" implies a much bigger learning curve than most people actually faced with the changes in the past. Yes, some people are greatly confused when, say, the control panel changes. But those people were already confused by the control panel. It's not as if these people were ultra-competent until the category view was added.
I actually agree that the control panel change is annoying, though. I think it was a bad change, because it's not merely different. I think it's actually less usable.
And yes, the change from Win7 to Win8 is massive. Not a lot of people would dispute that.
Literally having to re-learn the OS is almost certainly an over-statement with pre-win8 versions, as you are correct base functionality in previous versions is in many ways consistent.
However, how I interpret that statement is that it is ill-advised to over-estimate the general computer user's ability to adapt to changes, or the way 'little' changes end up disrupting the way they interact with the OS.
I might be interpreting OP's statement with my own bias, or reading into it too much, and we could probably go back and forth on semantics all day.
Regarding the control panel, I think the search functionality, which again a lot of non-techies may not even realize is an option, is the main redeeming quality and makes it much less aggravating to work with.
I took the statement about re-learning the OS to imply that every Windows release has had a massive change in interaction, similar to Windows 8. Based on run4yourlives's later reply, my interpretation seems correct.
I agree that it is dangerous to overestimate the general user's ability to adapt to changes. Microsoft does a lot of focus groups for this very reason. I don't think that Microsoft can cripple itself by never changing the interface, though. Maintaining an identical interface might work for a while, but eventually competitors who weren't afraid to innovate on the UI would win.
I agree about the control panel as well. Search fixes a lot of the issues. I'm glad Windows 8 has kept search working (and arguably improved it).