The problem was with the apksigner of the ADT package I downloaded(the official version from the website I might add). I exported an unsigned apk, used the 'apk-signer' utility(http://www.haibison.com/apps/apk-signer) to sign it, and sure enough it worked.
Not sure what is causing this issue.. I guess it's some kind of compatibility issue with my certificate because the fingerprint of the debug keystore did not change. And that one is generated by the ADT package.