Google Maps - "App won't run unless you update Google Play services"

Google Maps - "App won't run unless you update Google Play services"

I'm just trying to run the simple Google Maps tutorial here:
https://developers.google.com/maps/documentation/android/start
I'm running my app on my Nexus 4, and I receive the "update Google Play
services" message with an Update button. When I click the Update button,
it takes me to the Google Play services app on the Play Store, but it
appears that it's updated to the latest version.
Is there anything else I might be missing?
Android Manifest file:
<?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>