Essentially Matt Daley/Johnny Mohseni's solution worked for me.
I faced exactly the same problem on a fresh Android Studio V 1.2.1.1 installation. I created a new project (blank activity) and straightaway god this build error.
Error:Execution failed for task ':app:compileDebugAidl'.
> aidl is missing
As suggested, changing the gradle dependency from 1.2.3 to 1.3.0-beta1 fixed it.
classpath 'com.android.tools.build:gradle:1.3.0-beta1' // <--- WORKS!
//classpath 'com.android.tools.build:gradle:1.2.3' // <--- default - failed
Once 1.3.0-beta1 change was saved, I got a prompt to upgrade dependencies. Upon accepting the request to upgrade, the gradle build status bar at the bottom tracked the packages being synced. When that completed, the build was automatically triggered and completed successfully.