fatal: The upstream branch of your current branch does not match the name of your current branch

After doing a checkout of the remote branch releases/rel_5.4.1 using the Git GUI, I'm seeing this unexpected error message when I try to push:

fatal: The upstream branch of your current branch does not match
the name of your current branch.  To push to the upstream branch
on the remote, use

    git push origin HEAD:releases/rel_5.4.1

To push to the branch of the same name on the remote, use

    git push origin rel_5.4.1

I don't know what Git is talking about. I probably want to push to origin releases/rel_5.4.1 since that's the branch which I checked out. So neither option seems correct to me.

git status says I'm on branch rel_5.4.1.

Here is the branch as it appears in my .git/config:

[branch "rel_5.4.1"]
    remote = origin
    merge = refs/heads/releases/rel_5.4.1

What is going on?

This happens if the name of the upstream branch and local branch do not match, which sometimes happens, and usually is unwanted:

> git status
On branch release-1.2.3
Your branch is up to date with 'origin/master'.

To solve this, run:

git branch --unset-upstream

Then, once you run git push again, you will be asked to use the --set-upstream option to set the upstream branch correctly.

ATTENTION! While this answer has the most votes and is technically correct, it suggests that the problem is the push.default option, when usually the real problem is an unintended mismatch between the names of the local branch and the upstream branch. blindly following the instructions in this answer may cause your changes to be pushed to the wrong branch! For a safe quick fix, please see https://stackoverflow.com/a/24865780/2279059 instead.

For the benefit of the readers who might miss the probably most important detail, well hidden in the comments:

This is due to the git config push.default setting. It defines what git does when you enter git push (see link).

In the question, apparently the setting was set to simple (which is the default for git v2), probably with

git config --global push.default simple

This means, that git refuses to push when the local and remote branch do not match exactly.

As @TomSpurling notes, above setting is safer and recommended for normal use, because usually you want the same names for your local and remote branches.

However in certain situations, when your local branch is tracking some different remote branch with a different name, then you want to change that:

To allow to push to the tracking branch on a per-git basis, thus make git pull and git push symmetric, use

git config push.default upstream

Note: To globally set this for all of your gits, use git config --global push.default upstream
However it is probably better to leave it to git config --global push.default simple and only set this option in those workloads, where it is really required.