If a remote branch has been deleted, your local repository has to be told to prune the reference to it.
To prune deleted branches from a specific remote:
git fetch [remote-name] --prune
To prune deleted branches from all remotes:
git fetch --all --prune