I'm the author of this answer on StackOverflow. It seems to me like everyone in this post on SO is united in something that just seems very wrong to me. I'm clearly the minority here, but am I wrong? I'd like to hear your thoughts.
Don't worry, I'm not united! I agree with your conclusions. If I were still on SO, you'd get my upvote. But I'm not, so you'll have to have one here.
I gave up on git rebase after getting exactly the problem you describe, when trying to rebase my temp branch (with new stuff, including files that were entirely commented out in one commit then deleted in the next) on top of my main branch (with fixes to stuff the temp branch deletes or changes). I'd rebased things before, mostly because I'd heard it was what you were supposed to do, and it hadn't been a problem those times, but this time was awful!
Lots of tiresome conflicts, as git kept badgering me about merge conflicts due to one branch commenting out what another branch had changed, all in a file that would be deleted by the next commit. Of course, none of this crops up during a merge, because it only needs to consider the results rather than each intermediate step - so the merge ended up being much neater. (I think there ended up being fewer merge conflicts across the whole merge than there were in one file in the first step of the rebase.)
The idea behind this was that I'd rebase, then use rebase -i to remove the separate cleanup steps, then I could merge into the main branch, and it would be a nice fast-forward. I don't like the idea of using rebase -i until I've got something rebased as it stands, but it seems that git isn't always going to make that easy.
Since then, I've stuck with git merge, and indeed I've come to quite like seeing where the merges are in the history. That was something I found useful about Perforce's Revision Graph display, too.
Rebase gives people who have not fully embraced the DAG nature of DVCS warm fuzzies because it lets them keep their history "clean". I think rebase is typically a terrible idea because it invalidates any testing (or even basic sanity checking) that you do when you make commits. Once you rebase, your commits are no longer the same and therefore your previous testing is invalid.
