En principio el tienes que hacer un pull y luego un checkout. Si haces el checkout directamente no se entera que en origin (remoto) ya has actualizado la rama.
Entonces haces:
git pull
Deberías ver que al hacer el pull te dice que existe una nueva rama. Aparecerá algo como " * [new branch] nueva_rama -> origin/nueva_rama"
Luego deberías poder hacer el checkout a esa nueva rama existente en remoto:
git checkout nueva_rama
Si no te funciona, puedes probar a hacer esto:
git checkout --track origin/nueva_rama