This is an answer provided in a GitHub Issue that is preserved here.
An actual solution, for those breaking vim/macvim after "brew cleanup".
This will work if the current python is not the one your current vim/gvim/mvim is not linked to, check your vim and macvim version info (these might be separate homebrew packages), also make sure you update our brew so you'd use the latest packages:
mvim --version
vim --version
You'd know what is the linked python library:
-L/usr/local/Cellar/python/2.7.10_1/Frameworks/Python.framework/Versions/2.7/lib/python2.7/config
At this point that path is expected to be valid, hence the actual issue, In this case python 2.7.10_1 Cellar's is expected, now check your latest brew python package version:
brew info python
As you already confirmed the link path is valid (e.g. ls /usr/local/Cellar/python/), above command will show which is the active one, see top of output:
https://www.python.org
/usr/local/Cellar/python/2.7.10_2 (4943 files, 77M) *
Make sure python symlinks are fine:
brew unlink python && brew link --force python
And finally, re-build vim or macvim:
brew uninstall macvim && brew install macvim
Rebuilding is better than brew install --force, if you have the latest package, which I think is the case as that was the reason of a homebrew clean up.
Test your vim now
mvim --version
...
Compilation: ...
-L/usr/local/Cellar/python/2.7.10_2/Frameworks/Python.framework/Versions/2.7/lib/python2.7/config
Now :python print "hello" should work on your mvim. Do the same for command line vim if required.