Problem: You deleted a local branch and also on remote but you still see it when you do git branch -r. Use following to synchronize your branches:
git fetch -p
The -p flag means "prune". After fetching, branches which no longer exist on the remote will be deleted.