You need to add the following in your manifest:
<application>
<meta-data
android:name="com.google.android.gms.version"
android:value="@integer/google_play_services_version" />
...
</application>
EDIT:
This information can be found in the logcat error msg as well as on Setting Up Google Play Services (Thanks Brais Gabin)