Is there a quick way to relink my homebrew kegs?

/usr/local/Library/LinkedKegs seems to contain a list of, well, linked kegs, so this should do the trick:

ls -1 /usr/local/Library/LinkedKegs | while read line; do
    echo $line
    brew unlink $line
    brew link --force $line
done

I'd recommend ensuring you have write permissions to /usr/local/lib again before trying this.

This bash command (taken from there) will unlink all installed formulas and then link them again:

brew list -1 | while read line; do brew unlink $line; brew link $line; done

I guess all formulas need to be linked, otherwise, whichever tool depends on them, won't be able to find them..

In addition to the other answers to this question, you may also need to relink formula with multiple versions installed (brew link won't do this for you).

First, relink all the formulas you can:

brew list -1 | while read line; do brew unlink $line; brew link --force $line; done

Then run brew doctor, which should complain and give you two lists:

• Unlinked formulae with multiple versions
• Keg-only formulae which have been incorrectly link by the original relinking process.

For each formula with multiple versions run the following, replacing "python" with the formula name:

brew info python  

This will show you, among other information, all installed versions. Choose which version you want to link (for me its 2.7.6), and use brew switch

brew switch python 2.7.6

You will also want to run brew unlink on the list (if any) of keg-only formulae that have been linked.