I have built a new build configuration. Then the error has changed to INSTALL_FAILED_DEXOPT. Then I have restarted ADB, and the error became INSTALL_FAILED_UID_CHANGED again.
There is some problem in your configuration (you are the only developer to encounter this issue). Maybe it is your antivirus software? Try to disable it.
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.