In my case, adding testCompile 'com.google.appengine:appengine-tools-sdk:1.9.24'
to my build.gradle fixed it. (I'm using gradle - the maven equivalent should be the same.) Here are my test dependencies:
// Test
testCompile "junit:junit:4.12"
testCompile 'com.google.appengine:appengine-testing:1.9.24'
testCompile 'com.google.appengine:appengine-api-labs:1.9.24'
testCompile 'com.google.appengine:appengine-api-stubs:1.9.24'
testCompile 'com.google.appengine:appengine-tools-sdk:1.9.24'
I don't know what changed - it used to work without that dependency. But at least that seams to solve the problem.