Ok, I posted this a while ago in the comments. Just adding it here to mark the question answered:
Ok. I figured this out. Versions 0.4.3 and above have a bug in them See github.com/ahupp/python-magic/issues/44. I could not install it from pip(did pip-review --interactive, it shows me there is version 0.4.6 but won't install it). Since the bug was fixed in version 0.4.6 I got the python-magic.egg from pypi and installed it with easy_install, and it works!!!