매니페스트 GCM쪽에 패키지네임바꾸셨나요?
<permission
android:name="패키지명.permission.C2D_MESSAGE"
android:protectionLevel="signature" />
<uses-permission android:name="패키지명.permission.C2D_MESSAGE" />
<!-- GCM SERVICE -->
<receiver
android:name="com.google.android.gcm.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="패키지명" />
</intent-filter>
</receiver>
그리고 GCMBaseIntentService 상속받는 클래스는 디폴트패키지에 위치해있어야합니다