Okay so all I needed to do was add the -r to the rm command part (as below). I guess this is because bin is a directory rather than a file, so it must be removed recursively as otherwise the files it contains (or the information about them) would be orphaned.
$ git filter-branch --force --index-filter \
'git rm --cached -r --ignore-unmatch bin' \
--prune-empty --tag-name-filter cat -- --all
I followed this with the below to push the changes to the remote repo on github
$ git push origin master --force