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)