SERVICE_NOT_AVAILABLE some devices on Android GCM

SERVICE_NOT_AVAILABLE some devices on Android GCM

I made an app using GCM for notifications. I used this tutorial and my
code is pretty much identical
http://developer.android.com/google/gcm/client.html
I'm testing on physical devices and on some of the devices I am getting a
SERVICE_NOT_AVAILABLE error when I try to register the device with GCM.
I have an exponential backoff setup so it does retry over time.
It works on about half of my test devices the others get a
SERVICE_NOT_AVAILABLE error. Looked all over and haven't found a solution
yet.
Any help would be greatly appreciated. Thank You!