I had a slightly different but similar issue, but the solution might be useful to others who stumble on this question…
I noticed that my local repository still had remote branches that no longer existed on the remote, so I wanted to remove them. The solution is simply to fetch with the --prune (or -p) option:
git fetch --prune