I inherited an application that already implemented GCM services and is working well enough.
I'm saying well enough because half the times, when the app launches, I get the error INVALID_SENDER and the other half I don't get it!
There is no difference between the times I get the error and the times I don't (or maybe I'm missing the difference).
I do get messages from GCM from time to time (when I don't get the INVALID_SENDER after logging in) 
This is the registration code in the onCreate() of my main activity
private void registerGCM() throws Exception {
    GCMRegistrar.checkDevice(this);
    GCMRegistrar.checkManifest(this);
    registerReceiver(mHandleMessageReceiver, new IntentFilter(
            CommonUtilities.DISPLAY_MESSAGE_ACTION));
    final String regId = GCMRegistrar.getRegistrationId(this);
    if (regId.equals("")) {
        // Automatically registers application on startup.
        GCMRegistrar.register(this, CommonUtilities.SENDER_ID);
    } else {
        // Device is already registered on GCM, check server.
        if (GCMRegistrar.isRegisteredOnServer(this)) {
            ServerUtilities.register(mContext, regId);
        } else {
            // Try to register again, but not in the UI thread.
            // It's also necessary to cancel the thread onDestroy(),
            // hence the use of AsyncTask instead of a raw thread.
            final Context context = this;
            mRegisterTask = new AsyncTask<Void, Void, Void>() {
                @Override
                protected Void doInBackground(Void... params) {
                    boolean registered = ServerUtilities.register(context,                      regId);
                    if (!registered) {
                         GCMRegistrar.unregister(context);
                    }
                    return null;
                }
My Manifest file
 <receiver
        android:name="com.mixpanel.android.mpmetrics.GCMReceiver"
        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="com.says.broadcaster" />
        </intent-filter>
    </receiver>
    <receiver
        android:name="com.google.android.gcm.GCMBroadcastReceiver"
        android:permission="com.google.android.c2dm.permission.SEND" >
        <intent-filter>
            <!-- Receives the actual messages. -->
            <action android:name="com.google.android.c2dm.intent.RECEIVE" />
            <!-- Receives the registration id. -->
            <action android:name="com.google.android.c2dm.intent.REGISTRATION" />
            <category android:name="com.says.broadcaster" />
        </intent-filter>
    </receiver>
The reason I have two receivers is that I get push notifications from the stats tracking API I'm using too, and they use GCM.
My app has a new version every week or so, and I was reading that I need to register for a new ID after an app update. Could this be the issue?
Related questions: Getting INVALID_SENDER on one device while its working with another GCM android