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 brew update-reset.
This happened to me today and I spent way too long looking for the solution.
[Source: GitHub comment by @joshuapinter]