По сути, решение Мэтта Дейли / Джонни Мохси работало для меня.
Я столкнулся с такой же проблемой на новой установке Android Studio V 1.2.1.1.
Error:Execution failed for task ':app:compileDebugAidl'.
> aidl is missing
Как было предложено, изменение зависимости градиента от 1.2.3 до 1.3.0-beta1 фиксировало его.
classpath 'com.android.tools.build:gradle:1.3.0-beta1' // <--- WORKS!
//classpath 'com.android.tools.build:gradle:1.2.3' // <--- default - failed
После того, как было изменено изменение 1.3.0-beta1, я получил запрос на обновление зависимостей. После принятия запроса на обновление в строке состояния построения градиента внизу отслеживаются синхронизированные пакеты. Когда это завершено, сборка автоматически запускается и завершается успешно.