If you get this message after doing a git pull remote branch, try following it up with a git fetch. (Optionally, run git fetch -p to prune deleted branches from the repo)
Fetch seems to update the local representation of the remote branch, which doesn’t necessarily happen when you do a git pull remote branch.