Google Play Services - Google login yields a network error

I am trying to integrate Google Play Services into my application in order to enable achievements. Upon application launch, a login attempt is being made which results in one of the following errors:

1. There was a problem communicating with Google servers.
2. Failed to log in. Please check your network connection and try again later.
3. A̶p̶p̶l̶i̶c̶a̶t̶i̶o̶n̶ ̶c̶r̶a̶s̶h̶e̶s̶
4. The application is incorrectly configured. Check that the package name and signing certificate match the cliend ID created in Developer console. Also, if the application is not yer published, check that the account you are trying to sign in with is listed as a tester account. See logs for more information.

Logcat displays absolutely no data related to this problem so I don't even have a clue what could be wrong. The app is authenticated correctly, with the correct SHA1 certificate fingerprint and app id copied to manifest. Does anyone have any could what this could be? Thanks.

EDIT: Manifest:

<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
    package="com.*****.xxx"
    android:versionCode="1"
    android:versionName="1.0" >

    <uses-sdk
        android:minSdkVersion="11"
        android:targetSdkVersion="21" />

    <uses-permission android:name="android.permission.INTERNET" />
    <uses-permission android:name="android.permission.ACCESS_NETWORK_STATE" />
    <uses-permission android:name="android.permission.READ_PHONE_STATE" />
    <uses-permission android:name="android.permission.WRITE_EXTERNAL_STORAGE" />
    <uses-permission android:name="android.permission.ACCESS_WIFI_STATE" />
    <uses-permission android:name="android.permission.ACCESS_COARSE_LOCATION" />
    <uses-permission android:name="android.permission.ACCESS_FINE_LOCATION" />

    <application
        android:allowBackup="true"
        android:icon="@drawable/ic_launcher"
        android:label="@string/app_name"
        android:theme="@style/AppTheme" >
        <activity
            android:name="com.example.app.Main"
            android:label="@string/app_name"
            android:screenOrientation="portrait"
            android:theme="@style/NoActionBar" >
            <intent-filter>
                <action android:name="android.intent.action.MAIN" />

                <category android:name="android.intent.category.LAUNCHER" />
            </intent-filter>
        </activity>
        <activity
            android:name="com.example.app.GameAct"
            android:label="@string/title_activity_game"
            android:screenOrientation="portrait" >
        </activity>

        <meta-data
            android:name="com.google.android.gms.games.APP_ID"
            android:value="@string/app_id" />
        <meta-data
            android:name="com.google.android.gms.version"
            android:value="@integer/google_play_services_version" />



    </application>

</manifest>