Google Maps: "La aplicación no se ejecutará a menos que actualice los servicios de Google Play"

Sólo estoy intentando ejecutar el sencillo tutorial de Google Maps aquí: https://developers.google.com/maps/documentation/android/start

Estoy ejecutando mi aplicación en mi Nexus 4, y recibo el mensaje "Actualizar los servicios de Google Play" con un botón Actualizar. Cuando hago clic en el botón Actualizar, me lleva a la aplicación de servicios de Google Play en Play Store, pero parece que se ha actualizado a la última versión.

• Importación de google-play-services lib en Intellij IDEA 12 (y 13)
• Metadatos de error de Google Play Services v13 en AndroidManifest
• import lib google.android.gms "No se pudo encontrar la clase" después de actualizar sdk y google-api
• API de Android Places: Servicios de Google Play desactualizados en el emulador
• Gcm GoogleCloudMessaging nueva implementación

¿Hay algo más que podría estar perdiendo?

Archivo de manifiesto de Android:

<?xml version="1.0" encoding="utf-8"?> <manifest xmlns:android="http://schemas.android.com/apk/res/android" package="com.example.ridenotifier" android:versionCode="1" android:versionName="1.0" > <uses-permission android:name="android.permission.READ_CONTACTS" /> <uses-permission android:name="android.permission.SEND_SMS" /> <uses-permission android:name="android.permission.RECEIVE_SMS" /> <uses-permission android:name="android.permission.ACCESS_FINE_LOCATION" /> <uses-sdk android:minSdkVersion="11" android:targetSdkVersion="16" /> <application android:allowBackup="true" android:icon="@drawable/ic_launcher" android:label="@string/app_name" android:theme="@style/AppTheme" > <uses-library android:name="com.google.android.maps" /> <activity android:name="com.example.ridenotifier.MainActivity" android:label="@string/app_name" > <intent-filter> <action android:name="android.intent.action.MAIN" /> <category android:name="android.intent.category.LAUNCHER" /> </intent-filter> </activity> <activity android:name="com.example.ridenotifier.ContactListActivity" android:label="@string/title_activity_contact_list" > </activity> <meta-data android:name="com.google.android.maps.v2.API_KEY" android:value="AIzaSyATNKboMr-94m9GUWOlLkEgApQW4uvh4Js" /> </application> </manifest> 

Captura de pantalla:

**

 <permission android:name="yourpackageName.permission.MAPS_RECEIVE" android:protectionLevel="signature"/> <uses-permission android:name="yourpackageName.permission.MAPS_RECEIVE"/> <uses-permission android:name="android.permission.INTERNET"/> <uses-permission android:name="android.permission.WRITE_EXTERNAL_STORAGE"/> <uses-permission android:name="com.google.android.providers.gsf.permission.READ_GSERVICES"/> <uses-permission android:name="android.permission.ACCESS_COARSE_LOCATION"/> <uses-permission android:name="android.permission.ACCESS_FINE_LOCATION"/>