Thanks to everyone for suggestion! This is what was actually happening:
Because the APK is of a Hybrid application, it contained JS files. We transported the APK via email between the two machines. Apparently the Microsoft Exchange Server decides to check the insides of APK for 'dangerous' files and it did so, found a bunch of 'dangerous' JS files, removed all JS files and replacing them with helpful text files explaining it's actions. Therefore the APK would no longer install as it was tampered with by Microsoft Exchange. Obviously we didn't notice that at first as we didn't expect anything to be tampering with the APK.