If you run
brew update and see output that looks like this:
fatal: It seems that there is already a rebase-merge directory, and I wonder if you are in the middle of another rebase. If that is the case, please try git rebase (--continue | --abort | --skip) If that is not the case, please rm -fr ".git/rebase-merge" and run me again. I am stopping in case you still have something valuable there. Already up-to-date.
You can fix it by running
This happened to me today and I spent way too long looking for the solution.
[Source: GitHub comment by @joshuapinter]