I encountered the same exact error message. I am not quite sure if my solution will solve also your issue.
In Project Structure (app) I changed the Compile SDK Version from API 22 to API 21 and changed Build Tools Version from 22.0.0 to 21.1.2.
When I downloaded the latest API 22 Adroid 5.1, every project I create is using this API and causes me the problem. Maybe, Android Team is looking for a fix for this one.