I got the same problem, but things got complicated when I added few other libraries like appcompat.v7, recyclerView, CardView.
Removing appcompat.v4 from lib did not work for me.
I had to create project from start and first step I did is to remove appcompat.v4 from libs folder, and this worked.
I had just started the project so creating a new project wasn't a big issue for me!!!