none of the above worked for me. My situation is slightly different, my remote branch is not at origin. but in a different repository.
git remote add remoterepo GIT_URL.git
git fetch remoterepo
git checkout -b branchname remoterepo/branchname
tip: if you don't see the remote branch in the following output git branch -v -a
there is no way to check it out.
Confirmed working on 1.7.5.4