In my current repo I have the following output:
$ git branch -a
$ git branch -d remotes/public/master
error: branch 'remotes/public/master' not found.
$ git remote show
$ git push public :master
fatal: 'public' does not appear to be a git repository
fatal: The remote end hung up unexpectedly
You might be needing a cleanup
git gc --prune=now
or you might be needing a prune
git remote prune public
Deletes all stale 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/<name>".
With --dry-run option, report what branches will be pruned, but do no actually prune them.
However, it appears these should have been cleaned up earlier with
git remote rm public
Remove the remote named <name>. All remote tracking branches and configuration settings for the remote are removed.
So it might be you hand-edited your config file and this did not occur, or you have privilege problems.
Maybe run that again and see what happens.
If you take a look in the revision logs, you'll note I suggested more "correct" techniques, which for whatever reason didn't want to work on their repository.
I suspected the OP had done something that left their tree in an inconsistent state that caused it to behave a bit strangely, and
git gc was required to fix up the left behind cruft.
git branch -rd origin/badbranch is sufficient for nuking a local tracking branch , or
git push origin :badbranch for nuking a remote branch, and usually you will never need to call