I was able to run zipalign successfully by executing it directly from the build-tools directory.
In my case, the zipalign executable that worked fine was under /usr/local/Cellar/android-sdk/r20.0.3/build-tools/20.0.0/zipalign. Using that executable got my app signed in less than 10 seconds.
Then I just created a symlink so I could simply do zipalign in my terminal:
ln -sf /usr/local/Cellar/android-sdk/r20.0.3/build-tools/20.0.0/zipalign /usr/local/bin/zipalign
For those that have never seen zipalign working (like me), it takes a couple of seconds to run completely for my app (~8MB) and it outputs the files that are being compressed:
$ zipalign -v 4 MyAwesomeApp-release-unsigned.apk MyAwesomeApp.apk
Verifying alignment of MyAwesomeApp.apk (4)...
50 META-INF/MANIFEST.MF (OK - compressed)
9974 META-INF/GGRGOOGL.SF (OK - compressed)
20132 META-INF/GGRGOOGL.RSA (OK - compressed)
21317 assets/www/css/fonts/ITCAvantGardeStd-Bk.otf (OK - compressed)
44346 assets/www/css/fonts/ITCAvantGardeStd-BkCn.otf (OK - compressed)
67341 assets/www/css/fonts/ITCAvantGardeStd-BkCnObl.otf (OK - compressed)
....
6717884 res/drawable-port-mdpi/screen.png (OK)
6810380 res/drawable-port-xhdpi/screen.png (OK)
7311427 classes.dex (OK - compressed)
Verification succesful