I have never understood the problem that some people have with the idea of rewriting history. It's as if the very idea of it offends them. Do file system writes also put you off? Is it important that I see the history of every single keystroke you made while twiddling with your config file? When you fixed a typo you made in a comment before publishing your change, how is this not a "rewrite of history for aesthetic reasons"? Do you really need to know about all the tens of little WIP commits I made because I just wanted to back up my changes before going to the bathroom? Am I not allowed to clean up a little bit before I publish all my own changes to the world?
Now if you're just talking about rewriting published history, then nobody is going to disagree with you.
It's taken me a while to come around, but you'd have to pry rebase out of my cold dead hands now.
I have not found it to happen often though, for two reasons. First, it is widely agreed upon among almost all mildly experienced to highly experienced Git users that rewriting published history is a bad thing. Second, if it becomes a problem with new Git users doing this, you can turn of non-ff updates in the public repository, thereby disallowing this to ever happen, unless you go through all the steps to delete and recreate a branch.
If you're working with your local unpublished history, then it is your responsibility to make sure they still make sense in the context of newer updates from the public repo regardless of whether you rebase or merge. I can see how it would be confusing if people failed at this. I tend to find that more confusion results from people inflating the history with loads of one-commit merge bubbles everywhere rather than just rebasing their small changes.
Git is typical of a tool built by engineers. It has good primitives but a clunky overall design and horrible UI. It does not naturally encourage the most effective modes of use. Hell, even the "best practices" of the git community are highly questionable (just rewrite history for aesthetic reasons, what could go wrong?).
Git is highly tuned to the use case of serving linux kernel development. Many other folks have figured out decent ways to use it effectively as well but don't mistake that for Git being an unquestionably good tool or for it being "easy". Sure, the core workflow is pretty straightforward, but the fact that the easy stuff is easy is not a ringing endorsement of a tool. Good tools make hard stuff easier and easy stuff trivial.
Make no mistake, I think there are lots of awesome parts of git, the most important being its distributed nature. It's trivial to setup a repository because everything is a repository. That's pretty potent, and git has some reasonably well engineered components inside of it which make it fast for many common use cases, which is fantastic. But a big part of why git has been so successful lately has been because it hasn't had a lot of competition. Much of the competition is either hugely expensive (perforce, TFS), doesn't match the use case (same), hugely outdated (SVN), or terrible (TFS). The main competition for git is Mercurial, and a big reason git won out over Hg is because of mindshare traction and network effect from linux kernel development and then github.
The biggest problem now is that so many git fans are afraid of criticizing git's shortcomings.