I've got the same problem. This thread popped up first when I've searched for it. Solved it (hoping so) by not using the Instant Run feature. Might not be the best solution but it works for now.
Just go to "File -> Settings -> Build, Execution, Deployement -> Instant Run" and just disable it. With this Android Studio builds from scratch each time but it's better than not building it right.
Mini rant: Almost each version of Android Studio comes with an annoying bug. They're about to release the version 2 but its beta is still buggy. I hope they stabilize the IDE in the near future.