Git: Cannot see new remote branch

Check whether .git/config contains

[remote "origin"]
    url = …
    fetch = +refs/heads/master:refs/remotes/origin/master

If so, change it to say

[remote "origin"]
    url = …
    fetch = +refs/heads/*:refs/remotes/origin/*

Then you should be able to use it:

$ git fetch
remote: Counting objects: …
remote: Compressing objects: ..
Unpacking objects: …
remote: …
From …
 * [new branch]            branchname -> origin/branchname
$ git checkout branchname
Branch branchname set up to track remote branch branchname from origin.
Switched to a new branch 'branchname'

First, double check that the branch has been actually pushed remotely, by using the command git ls-remote origin. If the new branch appears in the output, try and give the command git fetch: it should download the branch references from the remote repository.

If your remote branch still does not appear, double check (in the ls-remote output) what is the branch name on the remote and, specifically, if it begins with refs/heads/. This is because, by default, the value of remote.<name>.fetch is:

+refs/heads/*:refs/remotes/origin/*

so that only the remote references whose name starts with refs/heads/ will be mapped locally as remote-tracking references under refs/remotes/origin/ (i.e., they will become remote-tracking branches)