To answer the question literally (since GitHub is not in the question title), also be aware of this post over on superuser. EDIT: Answer copied here in relevant part, slightly modified for clarity in square brackets:
You're getting rejected because you're trying to delete the branch that your origin has currently "checked out".
If you have direct access to the repo, you can just open up a shell [in the bare repo] directory and use good old
git branch
to see what branch origin is currently on. To change it to another branch, you have to usegit symbolic-ref HEAD refs/heads/another-branch
.