If Homebrew was updated on Aug 10-11th 2016 and brew update always says Already up-to-date. you need to run: cd "$(brew --repo)" && git fetch && git reset --hard origin/master && brew update.

Please follow the general troubleshooting steps first:

Bug reports:

I am stuck in a weird catch-22 situation where brew ends up with a split brain.

default-macosx-1011:~ vagrant$ brew
-bash: brew: command not found
default-macosx-1011:~ vagrant$ /usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"
It appears Homebrew is already installed. If your intent is to reinstall you
should do the following before running this installer again:
    ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/uninstall)"
The current contents of /usr/local are bin Cellar etc Frameworks Homebrew include lib opt sbin share var
default-macosx-1011:~ vagrant$ 
default-macosx-1011:~ vagrant$ ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/uninstall)"
Failed to locate Homebrew!