If you are using Android Studio 2.0 Beta, this issue might appear (more likely if you are working on NTFS filesystem) and it seems like the "Instant Run" is the culprit. Search for "Instant Run" in settings and uncheck the box.
I have filed an issue on the bug tracker.