Rename remote git branch

Updating your local branch's tracking reference to the new remote is rather easy:

git branch -m old_branch new_branch         # Rename branch locally    
git push --set-upstream origin new_branch   # Push the new branch, set local branch to track the new remote
git push origin :old_branch                 # Delete the old branch    

Then each client should do the following:

git fetch origin
git remote prune origin