GCM SERVICE_NOT_AVAILABE only on cellular network

Question

Me and my friend are developing an Android app and implemented everything necessary for GCM. On my device (Nexus 4) the registration and receiving of messages work fine over WiFi and cellular network. But if my friend tries to register his device (Xperia Z) it fails over cellular network and he gets the SERVICE_NOT_AVAILABLE error. Over WiFi the registration and message receiving is working fine with his device too. If he registers his device on WiFi and then switches back to cellular data he is not receiving any message!

We don't have enough devices to test if it is a problem with his device or a problem in our app, so we hope you can help us. Here are some files of our project, if you need more details I will add them afterwards.

AndroidManifest.xml

<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
    package="de.mypackage.vorlesungsplan.app"
    android:versionCode="0010201"
    android:versionName="1.2.1 (Raw Potato)" >

    <uses-sdk
        android:minSdkVersion="8"
        android:targetSdkVersion="19" />
    <uses-permission android:name="android.permission.ACCESS_NETWORK_STATE"/>
    <uses-permission android:name="android.permission.INTERNET"/>
    <uses-permission android:name="android.permission.READ_PHONE_STATE"/>
    <uses-permission android:name="android.permission.WRITE_EXTERNAL_STORAGE"/>
    <uses-permission android:name="android.permission.READ_EXTERNAL_STORAGE"/>
    <uses-permission android:name="android.permission.ACCESS_WIFI_STATE"/>
    <uses-permission android:name="android.permission.GET_ACCOUNTS"/>
    <uses-permission android:name="android.permission.WAKE_LOCK" />
    <uses-permission android:name="com.google.android.c2dm.permission.RECEIVE"/>
    <uses-permission android:name="android.permission.GET_TASKS"/>
    <permission android:name="de.mypackage.vorlesungsplan.app.permission.C2D_MESSAGE"
        android:protectionLevel="signature" />
    <uses-permission android:name="de.mypackage.vorlesungsplan.app.C2D_MESSAGE" />
    <supports-screens android:normalScreens="true" android:xlargeScreens="true" android:largeScreens="true" android:smallScreens="false"/>

    <application
        android:icon="@drawable/ic_launcher"
        android:label="@string/app_name"
        android:theme="@style/AppTheme"
        android:allowBackup="false" >
        <activity
            android:name="MainActivity"
            android:label="@string/title_activity_startup" android:screenOrientation="portrait">
            <intent-filter>
                <action android:name="android.intent.action.MAIN" />
                <category android:name="android.intent.category.LAUNCHER" />
            </intent-filter>
        </activity>
        <activity android:name="SettingsActivity" android:label="Einstellungen" android:screenOrientation="portrait"></activity>
        <activity android:name="InfoHelpActivity" android:screenOrientation="portrait"></activity>
        <activity android:name="LunchActivity" android:screenOrientation="portrait"></activity>
        <meta-data android:name="com.google.android.gms.version"
           android:value="@integer/google_play_services_version"/>

        <receiver
            android:name=".io.GCMBroadcastReceiver"
            android:permission="com.google.android.c2dm.permission.SEND" >
            <intent-filter>
                <action android:name="com.google.android.c2dm.intent.RECEIVE" />
                <action android:name="com.google.android.c2dm.intent.REGISTRATION" />
                <category android:name="de.mypackage.vorlesungsplan.app" />
            </intent-filter>
        </receiver>
        <service android:name=".io.GCMIntentService" />
    </application>

</manifest>

The register() method is executed on a background process like the documentation pretends it. Therefore we used a normal Thread instead of AsyncTask, but I don't think that this could cause the problem. The following class extends the Thread class:

RegisterServerOperation.java

public void run() {
    ...

    if(checkPlayServices()) {
        Logbook.d("Device is GCM capable");

        // Hole die regId des Geräts oder erzeuge eine neue
        GoogleCloudMessaging gcm = GoogleCloudMessaging.getInstance(activity);
        String regId = Settings.getInstance(activity).getSetting("regId");

        if (regId == null || regId.isEmpty()) {
            regId = gcm.register(SENDER_ID);
            Settings.getInstance(activity).setSetting("regId", regId);
        }

        Logbook.d("Registration id for this device is: "+regId);
    } else {
        throw new Exception("REGISTRATION_FAILED");
    }

    ...
}

The checkPlayServices() method is copied from the Google example and should also be correct, because the "Device is GCM capable" string appears in logcat. The Settings class is our own implementation for holding settings and the Logbook class is only a wrapper class for android.util.Log. My friend also did a capture of his network traffic with DDMS:

The first peak was caused by a normal http-request that our app sends at the start. It proves that his cellular network connection was viable in this moment. After this there should be another peak caused by the gcm.register(...) method, but there is nothing.

We built the app with the following version of google_play_services_lib project:

<?xml version="1.0" encoding="utf-8"?>
<resources>
    <integer name="google_play_services_version">4132500</integer>
</resources>

The Google Play Services that are installed on his device are up-to-date (version 4.1.32). His Android version is 4.3 and it is a Sony stock ROM. My Nexus 4 is running with a nightly build of CM 11 (so it is Android 4.4.2).

Please remember that the same app is working correctly over wifi but not cellular network. This is just confusing for both of us and we have tried many problem-solving approaches but none of them improved our situation.

I hope someone can help us, thank you