I followed the instructions above by Gene in Android Studio 1.5.1 but it added this to my build.gradle file:
compile 'platforms:android:android-support-v4:23.1.1'
so I changed it to:
compile 'com.android.support:support-v4:23.1.1'
And it started working.