It looks like multiple libraries are including the core library files; I get a slightly different exception when I make a sample case, but it's the same cause. If I open up the External Libraries tab to look at what jars it's using, I see spring-android-core and spring-core, and if I open those up to see what classes are in them, I see that both contain org.springframework.core.ErrorCoded
(which is the duplicate class in my test case).

You're not including spring-core directly; it's coming in as a transitive dependency from the spring-android-auth library (if I include just those two libraries and omit spring-android-rest-template I still get the error). I tried digging through the pom file definitions in Maven Central to try to prove why it's happening, but I'm not sure I could give you an explanation that didn't have a lot of holes in it, so I'll stay quiet on that front ;-) But I won't lack of understanding get in the way of trying to fix the problem. If you tell the spring-android-auth dependency to exclude spring-core, it does the trick:
dependencies {
...
compile 'org.springframework.android:spring-android-rest-template:1.0.1.RELEASE'
compile('org.springframework.android:spring-android-auth:1.0.1.RELEASE') {
exclude module: 'spring-core'
}
compile 'org.springframework.android:spring-android-core:1.0.1.RELEASE'
}
I also came across this error:
Execution failed for task ':app:packageDebug'.
> Duplicate files copied in APK META-INF/notice.txt
File 1: /Users/sbarta/.gradle/caches/modules-2/files-2.1/org.springframework.android/spring-android-auth/1.0.1.RELEASE/f43faebbf90aef324979a81a4f5eee1e3b95191f/spring-android-auth-1.0.1.RELEASE.jar
File 2: /Users/sbarta/.gradle/caches/modules-2/files-2.1/org.springframework.android/spring-android-auth/1.0.1.RELEASE/f43faebbf90aef324979a81a4f5eee1e3b95191f/spring-android-auth-1.0.1.RELEASE.jar
so I had to follow the instructions at Android Gradle plugin 0.7.0: "duplicate files during packaging of APK" to exclude some META-INF/ files from packaging, and I added:
android {
...
packagingOptions {
exclude 'META-INF/notice.txt'
exclude 'META-INF/license.txt'
}
}