brew update should do it. You might be using too-old a version or hit an update bug. Try:

cd $(brew --repo); git fetch; git reset --hard origin/master; brew update