Update: Does not apply to the Android Studio released after this answer (April 2016)
Note: I think this might be a bug in Android Studio.
- Go to Project Structure
- Select App Module
- Under the first tab "Properties" change the Compile SDK Version to API XX from Google API xx (e.g. API 23 instead of Google API 23)
- Press OK
- Wait for the completion of on going process, in my case I did not get an error at this point.
Now revert Compiled Sdk Version back to Google API xx.
If this not work, then:
- With Google API (Google API xx instead of API xx), lower the build tool version (e.g. Google API 23 and build tool version 23.0.1)
- Press Ok and wait for completion of on going process
- Revert back your build tool version to what it was before you changed
- Press Ok
- Wait for the completion of process.
- Done!