I had the same issue. There was no directory called., /usr/local/Cellar but brew installation kept reporting it is already installed.
I resolved the issue by doing the following.,
Step 1 : run
rm -rf /usr/local/Cellar /usr/local/.git && brew cleanup
(It reported error and didn't run successfully., but I believe it did cleanup)
Step 2 : Being from Windows world., restarted the terminal
Step 3 : Ran again
ruby -e "$(curl -fsSL https://raw.github.com/mxcl/homebrew/go)"
It ran successfully.,