As mentioned by @Josh in a comment on Nathan McDaniel's Answer, this is likely due to the branch no longer existing in the remote repository. This causes git branch -a to still show the branch under origin (or whatever you happened to name this particular remote), but deleting the branch on the remote repository is impossible because it no longer exists on the remote. This could have been caused by deleting the branch on the remote from another computer (on top of the fact that git pull and git fetch do not remove references to remote branches that have been deleted from the remote repository).
The fix
Simply remove all remote-tracking branches that have already been removed from the remote repository with git remote prune:
git remote prune REMOTENAME
For example, if your remote's name is origin (likely), the above command would look like:
git remote prune origin
From the documentation provided with git:
git remote prune [-n | --dry-run] <name>
Deletes all stale remote-tracking branches under <name>. These stale branches have already been removed from the remote repository referenced by <name>, but are still locally available in "remotes/".
With --dry-run option, report what branches will be pruned, but do not actually prune them.