Creating an AVD image with Google APIs is a bit more complex than just having the packages available (which we do).
We just tested with a new project and this should work - delete the Create Android Emulator step and replace it with a Script step:
#!/bin/bash
set -e
set -x
echo y | android update sdk --no-ui --all --filter addon-google_apis-google-22