The correct solution seems to be to install gcc again. brew reinstall gcc somehow does not do the trick, but brew uninstall gcc, followed by brew install gcc does. I assume this runs the mkheader script mentioned in the comment by this user as well.