Rebase warning when running `brew update`

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]