Alternatively you could update brew
by installing it again. (Think I did this as El Capitan changed something)
Note: this is a heavy handed approach that will remove all applications installed via brew!
Try to install brew a fresh and it will tell how to uninstall.
At original time of writing to uninstall:
ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/uninstall)"
Edit: As of 2020 to uninstall:
/bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/uninstall.sh)"