Brew won't uninstall a package because it can't find another formula
First steps would be to brew update (twice) then brew doctor to make sure all is good in brew. Then check that the XCode command line tools and Xcode itself are up to date.

If, after that, you still get the problem you may have found a formula bug so file an issue at https://github.com/Homebrew/brew