The problem kept occurring… after digging deeper I found that only uninstalling Homebrew and then re-installing it solved this issue.
Uninstalling will remove all your brew packages, you can save the output of brew list in a file first, to have a record of what packages were installed.
Uninstall Homebrew:
/usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/uninstall)"
Then re-install it:
/usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/maste