I had the same problem but it wasn't the code (everithing was like yours, like the doc says: http://developer.android.com/google/gcm/client.html), it was the Eclipse project.
Check this if it could help you:
Do a refactor and move the service from one package to another. Check if the androidManifest.xml doesn't change the package automatically. If not then you have the same problem than me.
I solved it by removing the ServiceIntent class and creating a new one (with the same content). It appears that my service was disconnected or something like this, and for the time I realized that I had got crazy by comparing the code.
With the new one, if you check again you will see the package changing in the androidmanifest.xml and your service called by the GcmBroadcastReceiver!! :)