You are right! It was my ZoneAlarm Internet Security Suite. When I have disabled it, all applications started installing and working. Then I re-enabled the antivirus, but excluded files named classes.dex. Everything still works.
Thank you very much, Erel, for your help!